中级农民
- 积分
- 100
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-10-11
- 最后登录
- 1970-1-1
|
- /** Singly linked lists
- */
- public class SNode {
- public SNode next;
- public double val;
- public SNode(double val, SNode next) {
- this.next = next;
- this.val = val;
- }
-
- }
- /** Singly linked list
- */
- public class SList {
- public SNode head;
- public int size;
- /** insert a value val at position
- * destructive approach
- * if the position is invalid, insert the node at the end
- */
-
- public SList(double val) {
- head = new SNode(val, null);
- size = 1;
- }
- public SList() {
- this.head = null;
- size = 0;
- }
- public void insertBack(double val) {
- SNode p = head;
- if (head == null) {
- head = new SNode(val, null);
-
- } else {
- while(p.next != null) {
- p = p.next;
- }
- p.next = new SNode(val, p.next);
- size += 1;
- }
- }
- public void insert(double val, int position) {
- SNode p = head;
- if (position < 0 || position >= size){
- insertBack(val);
- } else if (position == 0) {
- head = new SNode(val, head);
- size += 1;
- } else {
- for(int i = 0; i < position - 1; i++) {
- p = p.next;
- }
- p.next = new SNode(val, p.next);
- size += 1;
- }
- }
-
- public void printList() {
- SNode p = head;
- while( p != null) {
- System.out.println(p.val);
- p = p.next;
- }
- }
-
- public static void main(String[] args) {
- SList list = new SList(5.0);
- list.insert(6, 1);
- list.insert(2, 2);
- list.insert(10, 1);
- list.insert(10, 0);
- int inValidPos1 = -1;
- int inValidPos2 = 5;
- list.insert(11, inValidPos1);
- list.insert(12, inValidPos2);
- list.printList();
- }
- }
- /** Insert elements into a SentinelList.
- * if the posiiton is invalid, insert the node at the end
- */
- public class SentinelSList {
- private SNode front;
- private SNode back;
- private int size;
- public SentinelSList() {
- this.back = new SNode(0, null);
- this.front = new SNode(0, back);
- this.size = 0;
- }
- public void printList() {
- SNode p = front.next;
- while( p != back) {
- System.out.println(p.val);
- p = p.next;
- }
- }
- public void insertBack(double val) {
- SNode p = front.next;
- if (p == back){
- front.next = new SNode(val, back);
- } else {
- while(p.next != back) {
- p = p.next;
- }
- p.next = new SNode(val, p.next);
- size += 1;
- }
- }
- public void insert(double val, int position) {
- SNode p = front.next;
- if (position < 0 || position >= size){
- insertBack(val);
- } else if (position == 0) {
- front.next = new SNode(val, front.next);
- size += 1;
- } else {
- for(int i = 0; i < position - 1; i++) {
- p = p.next;
- }
- p.next = new SNode(val, p.next);
- size += 1;
- }
- }
- public static void main(String[] args) {
- SentinelSList list = new SentinelSList();
- list.insert(6, 0);
- list.insert(2, 1);
- list.insert(10, 1);
- list.insert(10, 0);
- int inValidPos1 = -1;
- int inValidPos2 = 5;
- list.insert(11, inValidPos1);
- list.insert(12, inValidPos2);
- list.printList();
- }
- }
复制代码 |
|