707. 设计链表

题目具体描述见707

  1. class MyLinkedList {
  2.     class Node {
  3.         int val;
  4.         Node pre, next;
  5.         Node(){};
  6.         Node(int val) {
  7.             this.val = val;
  8.         }
  9.         Node(int val, Node pre, Node next) {
  10.             this.val = val;
  11.             this.pre = pre;
  12.             this.next = next;
  13.         }
  14.     }
  16.     Node head, tail;
  17.     int size;
  18.     public MyLinkedList() {
  19.         head = new Node(-1);
  20.         tail = new Node(-1);
  21.         head.next = tail;
  22.         tail.pre = head;
  23.         size = 0;
  24.     }
  26.     public int get(int index) {
  27.         if (index < 0 || index >= size)
  28.             return -1;
  29.         int reIndex = size - index - 1;
  30.         //一个小优化，根据index决定从前往后查询还是从后往前查询
  31.         if (index <= reIndex) {
  32.             Node cur = head;
  33.             while (index > 0) {
  34.                 cur = cur.next;
  35.                 index--;
  36.             }
  37.             return cur.next.val;
  38.         } else {
  39.             Node cur = tail;
  40.             while (reIndex > 0) {
  41.                 cur = cur.pre;
  42.                 reIndex--;
  43.             }
  44.             return cur.pre.val;
  45.         }
  47.     }
  49.     public void addAtHead(int val) {
  50.         Node node = new Node(val, head, head.next);
  51.         node.next.pre = node;
  52.         head.next = node;
  53.         size++;
  54.     }
  56.     public void addAtTail(int val) {
  57.         Node node = new Node(val, tail.pre, tail);
  58.         node.pre.next = node;
  59.         tail.pre = node;
  60.         size++;
  61.     }
  63.     public void addAtIndex(int index, int val) {
  64.         if (index <= 0)
  65.             addAtHead(val);
  66.         else if (index == size)
  67.             addAtTail(val);
  68.         else if (index > size)
  69.             return;
  70.         else {
  71.             int reIndex = size - index;
  72.             //一个小优化，根据index决定从前往后查询还是从后往前查询
  73.             if (index <= reIndex) {
  74.                 Node cur = head;
  75.                 while (index > 0) {
  76.                     cur = cur.next;
  77.                     index--;
  78.                 }
  79.                 Node node = new Node(val, cur, cur.next);
  80.                 node.next.pre = node;
  81.                 cur.next = node;
  82.                 size++;
  83.             } else {
  84.                 Node cur = tail;
  85.                 while (reIndex > 0) {
  86.                     cur = cur.pre;
  87.                     reIndex--;
  88.                 }
  89.                 Node node = new Node(val, cur.pre, cur);
  90.                 node.pre.next = node;
  91.                 cur.pre = node;
  92.                 size++;
  93.             }
  94.         }
  95.     }
  97.     public void deleteAtIndex(int index) {
  98.         if (index < 0 || index >= size)
  99.             return;
  100.         int reIndex = size - index - 1;
  101.         //一个小优化，根据index决定从前往后查询还是从后往前查询
  102.         if (index <= reIndex) {
  103.             Node cur = head;
  104.             while (index > 0) {
  105.                 cur = cur.next;
  106.                 index--;
  107.             }
  108.             cur.next = cur.next.next;
  109.             cur.next.pre = cur;
  110.             size--;
  111.         } else {
  112.             Node cur = tail;
  113.             while (reIndex > 0) {
  114.                 cur = cur.pre;
  115.                 reIndex--;
  116.             }
  117.             cur.pre = cur.pre.pre;
  118.             cur.pre.next = cur;
  119.             size--;
  120.         }
  121.     }
  122. }
  124. /**
  125.  * Your MyLinkedList object will be instantiated and called as such:
  126.  * MyLinkedList obj = new MyLinkedList();
  127.  * int param_1 = obj.get(index);
  128.  * obj.addAtHead(val);
  129.  * obj.addAtTail(val);
  130.  * obj.addAtIndex(index,val);
  131.  * obj.deleteAtIndex(index);
  132.  */