2.1 鏈表（coding）

08-23

2.1 鏈表（coding）

來自專欄數據機構與演算法——雜記

設計鏈表

設計鏈表的實現。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節點應該具有兩個屬性：val 和 next。val 是當前節點的值，next 是指向下一個節點的指針/引用。如果要使用雙向鏈表，則還需要一個屬性 prev 以指示鏈表中的上一個節點。假設鏈表中的所有節點都是 0-index 的。

在鏈表類中實現這些功能：

get(index)：獲取鏈表中第 index 個節點的值。如果索引無效，則返回-1。
addAtHead(val)：在鏈表的第一個元素之前添加一個值為 val 的節點。插入後，新節點將成為鏈表的第一個節點。
addAtTail(val)：將值為 val 的節點追加到鏈表的最後一個元素。
addAtIndex(index,val)：在鏈表中的第 index 個節點之前添加值為 val 的節點。如果 index 等於鏈表的長度，則該節點將附加到鏈表的末尾。如果 index 大於鏈表長度，則不會插入節點。
deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個節點。

示例：

MyLinkedList linkedList = new MyLinkedList();linkedList.addAtHead(1);linkedList.addAtTail(3);linkedList.addAtIndex(1,2); //鏈表變為1-> 2-> 3linkedList.get(1); //返回2linkedList.deleteAtIndex(1); //現在鏈表是1-> 3linkedList.get(1); //返回3

提示：

所有值都在 [1, 1000] 之內。
操作次數將在 [1, 1000] 之內。
請不要使用內置的 LinkedList 庫。

class ListNode{ public int val; public ListNode next; public ListNode(int x){ val = x; }}public class MyLinkedList { public ListNode head; public MyLinkedList() { this.head = null; } public int get(int index) { if(index >= length())return -1; ListNode node = head; int i = 0; while(i != index){ node = node.next; i++; } if(node == null)return -1; else return node.val; } public void addAtHead(int val) { ListNode node = new ListNode(val); node.next = head; head = node; } public void addAtTail(int val) { ListNode tail = new ListNode(val); ListNode node = head; if(node == null){ head = node; }else{ while(node.next != null){ node = node.next; } node.next = tail; } } public void addAtIndex(int index, int val) { if(index < 0 || index > length())return; if(index == 0) { addAtHead(val); return; } if(index == length()){ addAtTail(val); return; } if(index > length())return; ListNode in_node = new ListNode(val); ListNode cur = head; ListNode pre = head; int pole = 0; while(pole != index){ pre = cur; cur = cur.next; pole++; } in_node.next = cur; pre.next = in_node; } public void deleteAtIndex(int index) { if(head == null)return; if(index >= length())return; ListNode cur = head; ListNode pre = head; int pole = 0; while(pole != index){ pre = cur; cur = cur.next; pole++; } if(cur == pre){ head = head.next; }else{ pre.next = cur.next; } } public int length() { int length=0; ListNode temp = head; if(head == null)return 1; while(temp.next != null){ length++; temp = temp.next; } return length + 1; }}

測試代碼：

class ListNode{ public int val; public ListNode next; public ListNode(int x){ val = x; }}class MyLinkedList { public ListNode head; public MyLinkedList() { this.head = null; } public int get(int index) { ListNode node = head; int i = 0; while(i != index){ node = node.next; i++; } return node.val; } public void addAtHead(int val) { ListNode node = new ListNode(val); node.next = head; head = node; } public void addAtTail(int val) { ListNode tail = new ListNode(val); ListNode node = head; while(node.next != null){ node = node.next; } node.next = tail; } public void addAtIndex(int index, int val) { ListNode in_node = new ListNode(val); ListNode cur = head; ListNode pre = head; int pole = 0; while(pole != index){ pre = cur; cur = cur.next; pole++; } if(cur == pre){ in_node.next = head; head = in_node; }else{ in_node.next = cur; pre.next = in_node; } } public void deleteAtIndex(int index) { ListNode cur = head; ListNode pre = head; int pole = 0; while(pole != index){ pre = cur; cur = cur.next; pole++; } if(cur == pre){ head = head.next; }else{ pre.next = cur.next; } } public void display(){ ListNode cur = head; while(cur != null){ System. out.print(cur.val + " "); cur = cur.next; } System. out.println(); }}public class TestLinkList { public static void main(String[] args) { MyLinkedList linkList = new MyLinkedList(); linkList.addAtHead(20); linkList.display(); linkList.addAtHead(30); linkList.display(); System. out.println(linkList.get(0)); linkList.addAtTail(40); linkList.display(); linkList.addAtIndex(1, 1); linkList.display(); linkList.addAtIndex(3, 3); linkList.display(); linkList.addAtIndex(0, 4); linkList.display(); linkList.deleteAtIndex(0); linkList.display(); linkList.deleteAtIndex(1); linkList.display(); // MyLinkedList linkedList = new MyLinkedList();// linkedList.addAtHead(1);// linkedList.addAtTail(3);// linkedList.addAtIndex(1,2); //鏈表變為1-> 2-> 3// linkedList.get(1); //返回2// linkedList.deleteAtIndex(1); //現在鏈表是1-> 3// linkedList.get(1); //返回3 }}