链表理论基础

链表是通过指针串联的线性结构。每个节点 node 由数据 val 和指针域 next 两个部分组成。入口称为头结点，即 head。最后一个节点指向空指针 null。

• 双链表有两个指针域，指向 prev 和 next。
• 循环链表则是链表首尾相连。

链表在内存中并非连续分布。

链表在增删时候，复杂度 O(1)；查询访问时候复杂度 O(N)。适合频繁增删但并非频繁访问的场景。

注意记忆链表的定义。

C++ 单链表

struct ListNode {
    int val; // ListNode value
    ListNode *next; // pointer to next node
    ListNode(int x) : val(x), next(NULL) {} // Constructor of node
};

ListNode* head = new ListNode(5);

Python 单链表

class ListNode:
    def __init__(self, val: int, next=None):
        self.val = val
        self.next = next

203 移除链表元素 Remove Linked List Elements

题目：

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example 1:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

• The number of nodes in the list is in the range [0, 10^4].
• 1 <= Node.val <= 50
• 0 <= val <= 50

要点

1. 分类讨论是否是头节点，头节点的情况下，判断头节点是否是要删掉的值，再进一步对后面的节点进行操作。或者创建 dummy node 作为新的头节点，这样每一个节点都可以一致对待。
2. 注意 C++ 里新建一个链表节点时候 ListNode* dummy_node = new ListNode(val, next)，记得删除删掉的节点。使用 dummy node 的时候记得最后把 head 赋值成 dummy_node->next 并删掉 dummy node。

代码

常规分类讨论写法

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head != NULL && head->val == val) {
            // remove head node
            // ListNode* tmp = head;
            head = head->next;
            // delete tmp;
        }
        ListNode* curr_node = head;
        while (curr_node != NULL && curr_node->next != NULL) {
            if (curr_node->next->val == val) {
                ListNode* tmp = curr_node->next;
                curr_node->next = tmp->next;
                delete tmp;
            } else {
                curr_node = curr_node->next;
            }
        }
        return head;
    }
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        while head is not None and head.val == val:
            head = head.next
        curr_node = head
        while curr_node is not None and curr_node.next is not None:
            if curr_node.next.val == val:
                tmp = curr_node.next
                curr_node.next = tmp.next
            else:
                curr_node = curr_node.next 
        
        return head

dummy head 写法

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy_head = new ListNode(0, head);
        // dummy_head->next = head;
        ListNode* curr_node = dummy_head;
        while (curr_node != NULL && curr_node->next != NULL) {
            if (curr_node->next->val == val) {
                ListNode* tmp = curr_node->next;
                curr_node->next = tmp->next;
                delete tmp;
            } else {
                curr_node = curr_node->next;
            }
        }
        head = dummy_head->next;
        delete dummy_head;
        return head;
    }
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_node = ListNode(val=0, next=head)
        curr_node = dummy_node
        while curr_node is not None and curr_node.next is not None:
            if curr_node.next.val == val:
                tmp = curr_node.next
                curr_node.next = tmp.next
            else:
                curr_node = curr_node.next 
        
        head = dummy_node.next
        return head

707 设计链表 Design Linked List

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

• MyLinkedList() Initializes the MyLinkedList object.
• int get(int index) Get the value of the index^th node in the linked list. If the index is invalid, return -1.
• void addAtHead(int 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 addAtTail(int val) Append a node of value val as the last element of the linked list.
• void addAtIndex(int index, int val) Add a node of value val before the index^th node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
  void deleteAtIndex(int index) Delete the index^th node in the linked list, if the index is valid.

Example 1:

Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3
myLinkedList.get(1);              // return 2
myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3
myLinkedList.get(1);              // return 3

Constraints:

• 0 <= index, val <= 1000
• Please do not use the built-in LinkedList library.
• At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

要点

1. 注意什么情况下 invalid：index 大于等于 size。特别注意 get deleteAtIndex 的时候 invalid 是 大于等于 size。但 addAtIndex 不一样，是大于 size，因为末尾也可以添加。
2. 使用 dummy head 辅助能减少麻烦。但注意记得数 index 的时候不要算上它。
3. Python 灵活运用 while True 比如 while curr_node.next: 在单链表的情况下去找到末尾的 node。

代码

Python

class MyLinkedList:

    def __init__(self):
        self._dummy_head = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        
        curr_node = self._dummy_head.next
        for _ in range(index):
            curr_node = curr_node.next
            
        return curr_node.val

    def addAtHead(self, val: int) -> None:
        add_node = ListNode(val, next=self._dummy_head.next)
        self._dummy_head.next = add_node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        curr_node = self._dummy_head
        while curr_node.next:
            curr_node = curr_node.next
        curr_node.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return # the node will not be inserted
        curr_node = self._dummy_head
        for _ in range(index):
            curr_node = curr_node.next 
        curr_node.next = ListNode(val, next=curr_node.next)
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return # invalid
        curr_node = self._dummy_head
        for _ in range(index):
            curr_node = curr_node.next 
        curr_node.next = curr_node.next.next
        self.size -= 1


class ListNode:
    def __init__(self, val: int=0, next=None):
        self.val = val
        self.next = next

# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

C++

class MyLinkedList {
private:
    int size;
    ListNode* dummy_head;

public:
    MyLinkedList() {
        this->dummy_head = new ListNode(0);
        this->size = 0;
    }
    
    int get(int index) {
        if (index < 0 || index >= size) {
            return -1; // invalid
        }
        ListNode* curr_node = dummy_head;
        for (int i = 0; i <= index; i++) {
            curr_node = curr_node->next;
        }
        return curr_node->val;
    }
    
    void addAtHead(int val) {
        ListNode* add_node = new ListNode(val);
        add_node->next = dummy_head->next;
        dummy_head->next = add_node;
        size++;
    }
    
    void addAtTail(int val) {
        ListNode* add_node = new ListNode(val);
        ListNode* curr_node = dummy_head;
        while (curr_node->next != NULL) {
            curr_node = curr_node->next;
        }
        curr_node->next = add_node;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return; // invalid
        }
        ListNode* curr_node = dummy_head;
        for (int i = 0; i < index; i++) {
            curr_node = curr_node->next;
        }
        ListNode* add_node = new ListNode(val);
        add_node->next = curr_node->next;
        curr_node->next = add_node;
        size++; 
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return; // invalid
        }
        ListNode* curr_node = dummy_head;
        int count = index;
        while (count > 0) {
            curr_node = curr_node->next;
            count--;
        }
        ListNode* tmp = curr_node->next;
        curr_node->next = tmp->next;
        delete tmp;
        size--;
    }
};

// struct ListNode {
//     int val;
//     ListNode* next;
//     ListNode(int x) : val(x), next(NULL) {}
// };

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206 反转链表 Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

要点

1. 双指针法，注意需要留一个临时节点 next_node 来储存原本的下一个节点。注意快慢指针里，先更新 prev 再更新 curr。循环的条件是 while (curr_node != NULL) 这是因为，如果只停留在 curr_node->next != NULL 那会少把末尾节点连到倒数第二个上面。
2. 画图是辅助的办法，关注返回的到底是 prev 还是 curr。因为 curr 后面被更新到 next了而末尾的 next 是 NULL，所以反转后的头节点是 prev。

代码

双指针法

时间复杂度 O(N)，空间复杂度 O(1) (存储临时节点)

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* next_node; // store next node;
        ListNode* prev_node = NULL; // prev node;
        ListNode* curr_node = head;
        while (curr_node != NULL) { // curr_node != NULL instead of curr_node->next != NULL
            next_node = curr_node->next;
            curr_node->next = prev_node;
            // update prev and curr nodes
            prev_node = curr_node;
            curr_node = next_node;
        }
    return prev_node;
    }
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        prev = None
        while curr is not None:
            next_tmp = curr.next 
            curr.next = prev 
            # update curr and prev
            prev = curr
            curr = next_tmp 
        return prev

递归法比较复杂，暂时略过。