题目
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
示例：
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
解题:
看上面的示例就这可以知道，linkedList.addAtIndex(1,2)是要在索引为1的地方添加val=2的节点，也就是说当前节点要遍历到索引为0的位置。
linkedList.get(1)而这个方法，是要获得索引为1的地方的节点值，所以要遍历到索引为1的地方。因此可以看见在get的函数里面，for _ in range(index + 1)遍历中还要额外加一个1。
get中index 不能取到self.size,因为遍历中额外加1了。
addAtIndex中，index可以取到self.size,因为我们可以遍历到链表尾部，在尾部添加
deleteAtIndex中，index不能取到self.size,如果要删除尾节点，只要遍历到self.size-1就行了。
方法一：单链表
python解法
class ListNode: def __init__(self, x): self.val = x self.next = None class MyLinkedList: def __init__(self): self.size = 0 self.head = ListNode(0) # sentinel node as pseudo-head def get(self, index: int) -> int: """ Get the value of the index-th node in the linked list. If the index is invalid, return -1. """ # if index is invalid if index < 0 or index >= self.size: return -1 curr = self.head # index steps needed # to move from sentinel node to wanted index for _ in range(index + 1): curr = curr.next return curr.val def addAtHead(self, val: int) -> None: """ Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. """ self.addAtIndex(0, val) def addAtTail(self, val: int) -> None: """ Append a node of value val to the last element of the linked list. """ self.addAtIndex(self.size, val) def addAtIndex(self, index: int, val: int) -> None: """ Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. """ # If index is greater than the length, # the node will not be inserted. if index > self.size: return # [so weird] If index is negative, # the node will be inserted at the head of the list. if index < 0: index = 0 self.size += 1 # find predecessor of the node to be added pred = self.head for _ in range(index): pred = pred.next # node to be added to_add = ListNode(val) # insertion itself to_add.next = pred.next pred.next = to_add def deleteAtIndex(self, index: int) -> None: """ Delete the index-th node in the linked list, if the index is valid. """ # if the index is invalid, do nothing if index < 0 or index >= self.size: return self.size -= 1 # find predecessor of the node to be deleted pred = self.head for _ in range(index): pred = pred.next # delete pred.next pred.next = pred.next.next
c++解法
class MyLinkedList { public: /** Initialize your data structure here. */ MyLinkedList() { dummy=new ListNode(); length=0; } /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */ int get(int index) { if(index<0||index>length-1){ return -1; } ListNode* cur=dummy; for(int i=0;i<index+1;i++){ cur = cur->next; } return cur->val; } /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */ void addAtHead(int val) { addAtIndex(0,val); } /** Append a node of value val to the last element of the linked list. */ void addAtTail(int val) { addAtIndex(length,val); } /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */ void addAtIndex(int index, int val) { if(index>length) return; ListNode* cur=dummy; for(int i=0;i<index;i++){ cur = cur->next; } ListNode* newNode = new ListNode(val); newNode->next = cur->next; cur->next = newNode; // ListNode* tmp = cur->next; // cur->next = new ListNode(val,tmp); // cur->next->next = tmp; length++; } /** Delete the index-th node in the linked list, if the index is valid. */ void deleteAtIndex(int index) { if (index >= length || index < 0) { return; } ListNode* cur=dummy; for(int i=0;i<index;i++){ cur = cur->next; } cur->next = cur->next->next; length--; } public: ListNode* dummy; int length; };
java解法
public class ListNode{ int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val,ListNode next){this.val=val;this.next=next;} } class MyLinkedList { int length; ListNode dummy; public MyLinkedList() { length=0; dummy=new ListNode(0); } public int get(int index) { if(index<0||index>=length) return -1; ListNode cur=dummy.next; for(int i=0;i<index;i++){ cur=cur.next; } return cur.val; } public void addAtHead(int val) { addAtIndex(0,val); } public void addAtTail(int val) { addAtIndex(length,val); } public void addAtIndex(int index, int val) { if(index>length) return; ListNode cur=dummy; for(int i=0;i<index;i++){ cur=cur.next; } ListNode tmp=cur.next; cur.next=new ListNode(val); cur.next.next=tmp; length++; } public void deleteAtIndex(int index) { if(index<0||index>=length) return; ListNode cur=dummy; for(int i=0;i<index;i++){ cur=cur.next; } cur.next=cur.next.next; length--; } }
方法二：双链表
python解法
双链表中的插入操作
双链表中的删除操作
class ListNode: def __init__(self, x): self.val = x self.next, self.prev = None, None class MyLinkedList: def __init__(self): self.size = 0 # sentinel nodes as pseudo-head and pseudo-tail self.head, self.tail = ListNode(0), ListNode(0) self.head.next = self.tail self.tail.prev = self.head def get(self, index: int) -> int: """ Get the value of the index-th node in the linked list. If the index is invalid, return -1. """ # if index is invalid if index < 0 or index >= self.size: return -1 # choose the fastest way: to move from the head # or to move from the tail if index + 1 < self.size - index: curr = self.head for _ in range(index + 1): curr = curr.next else: curr = self.tail for _ in range(self.size - index): curr = curr.prev return curr.val def addAtHead(self, val: int) -> None: """ Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. """ pred, succ = self.head, self.head.next self.size += 1 to_add = ListNode(val) to_add.prev = pred to_add.next = succ pred.next = to_add succ.prev = to_add def addAtTail(self, val: int) -> None: """ Append a node of value val to the last element of the linked list. """ succ, pred = self.tail, self.tail.prev self.size += 1 to_add = ListNode(val) to_add.prev = pred to_add.next = succ pred.next = to_add succ.prev = to_add def addAtIndex(self, index: int, val: int) -> None: """ Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. """ # If index is greater than the length, # the node will not be inserted. if index > self.size: return # [so weird] If index is negative, # the node will be inserted at the head of the list. if index < 0: index = 0 # find predecessor and successor of the node to be added if index < self.size - index: pred = self.head for _ in range(index): pred = pred.next succ = pred.next else: succ = self.tail for _ in range(self.size - index): succ = succ.prev pred = succ.prev # insertion itself self.size += 1 to_add = ListNode(val) to_add.prev = pred to_add.next = succ pred.next = to_add succ.prev = to_add def deleteAtIndex(self, index: int) -> None: """ Delete the index-th node in the linked list, if the index is valid. """ # if the index is invalid, do nothing if index < 0 or index >= self.size: return # find predecessor and successor of the node to be deleted if index < self.size - index: pred = self.head for _ in range(index): pred = pred.next succ = pred.next.next else: succ = self.tail for _ in range(self.size - index - 1): succ = succ.prev pred = succ.prev.prev # delete pred.next self.size -= 1 pred.next = succ succ.prev = pred
在add和delete操作中，前向的时候index不再需要加1了，因为如果要插入，我们只要到该元素插入位置前即可。删除也是这样的。但是get就要到该元素的位置，因此index+1
而反向的时候，get,add,delete都是到达该索引原来的位置。只不过get是在当前元素的位置，add是在该元素前插入，delete也是删除该元素前的节点。
