链表全攻略

第一次接触链表的算法题，个人的整体感触是：多多画图，模仿指针的走法，弄清楚指针的先后移动顺序，明确指针的起始/停止方位和while跳出的停止条件。由于链表总是顺序移动的，所以while句子会常常遇到，特别是在寻觅长度时。

在这儿完成了用c++完成算法不报错的第一步，并尝试使用日志输出c++代码的中心进程来寻觅代码问题。

本篇blog将对day3&4打卡的全部内容进行梳理。 文章图来源于卡哥的代码随想录。

链表理论基础

链表扫盲

链表是一种通过指针串联在一起的线性结构，每个节点有两个部分组成，一个是数据域一个是指针域(寄存指向下一个节点的指针)，最终一个节点的指针域指向NULL（空指针）。

链表的头节点head是进入链接的进口节点。

Leetcode一刷-链表篇【补卡】-Day3&4/60

上图描绘的即为单链表，该类链表每个节点只有一个指向的指针。 c++完成的单链表结构体：

// 单链表
struct ListNode{
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的结构函数
}; // 最终面的这个分号不要忘记

其实c++会默许生成一个结构函数，可是这个结构函数会无法直接在初始化的时分给变量赋值。

// 运用自己写的结构函数，初始化节点
ListNode* head = new ListNode(5);  // 一个新的链表需求新开辟一个内存空间
// 运用默许的结构函数，初始化节点；
ListNode* head = new ListNode();
head->val = 5;

此处，弥补python的链表类：

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

链表和数组的不同之处，除了具有指针域之外，内存散布也不是连续的，而是散乱散布在内存中的某地址上，分配机制取决于操作系统的内存管理。

Leetcode一刷-链表篇【补卡】-Day3&4/60

链表操作

删去节点

  1. 将指向被删去节点的next指针指向下一个节点；
  2. 若运用c++，则需求手动开释被删去节点的内存。 ListNode * tmp = C->next; delete tmp;

Leetcode一刷-链表篇【补卡】-Day3&4/60

增加节点 链表的增加和删去都是O(1)操作，不会影响到其他节点，可是需求花O(n)的时刻复杂度，搜索指定方位的节点，由于节点总是从头开端查找的，使用next指针进行删去操作。

Leetcode一刷-链表篇【补卡】-Day3&4/60

与数组的比较

刺进/删去（时刻复杂度） 查询（时刻复杂度） 适用场景
数组 O(n) O(1) 数据量固定，频繁查询，较少增删
链表 O(1) O(n) 数据量不固定，频繁增删，较少查询

其他链表类型

双链表

  • 支撑向前向后查询，除了next之外，还有prev指针。

Leetcode一刷-链表篇【补卡】-Day3&4/60

循环链表

  • 首尾相连的链表

Leetcode一刷-链表篇【补卡】-Day3&4/60

Leetcode相关标题及解法要义

203. 移除链表元素

标题链接： leetcode.cn/problems/re…

此题是虚拟头节点的入门题，虚拟头节点的运用一般是为了防止链表对头节点的独自处理。最终回来的头节点是return dummyHead->next;

Leetcode一刷-链表篇【补卡】-Day3&4/60

c++运用虚拟头节点的思路：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后边做删去操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        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: ListNode, val: int) -> ListNode:
        dummy_head = ListNode(next=head) #增加一个虚拟节点
        cur = dummy_head
        while(cur.next!=None):
            if(cur.next.val == val):
                cur.next = cur.next.next #删去cur.next节点
            else:
                cur = cur.next
        return dummy_head.next

707. 设计链表

标题链接：leetcode.cn/problems/de…

此题共涉及了链表的五个接口

  • 获取链表第index个节点的数值；
  • 在链表的最前面刺进一个节点；
  • 在链表的最终面刺进一个节点；
  • 在链表第index个节点前面刺进一个节点；
  • 删去链表的第index个节点。

本题在初始化链表时需求加一个_size变量来记载链表的长度，同时，使用虚拟头节点ListNode *dummyHead = new ListNode(0)代替真实的头节点。

c++完成的单链表操作代码：

class MyLinkedList {
public:
    // 界说链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };
    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // 这儿界说的头结点 是一个虚拟头结点，而不是真实的链表头结点
        _size = 0;
    }
    // 获取到第index个节点数值，假如index是非法数值直接回来-1， 留意index是从0开端的，第0个节点便是头结点
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ // 假如--index 就会堕入死循环
            cur = cur->next;
        }
        return cur->val;
    }
    // 在链表最前面刺进一个节点，刺进完成后，新刺进的节点为链表的新的头结点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }
    // 在链表最终面增加一个节点
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }
    // 在第index个节点之前刺进一个新节点，例如index为0，那么新刺进的节点为链表的新头节点。
    // 假如index 等于链表的长度，则阐明是新刺进的节点为链表的尾结点
    // 假如index大于链表的长度，则回来空
    // 假如index小于0，则置为0，作为链表的新头节点。
    void addAtIndex(int index, int val) {
        if (index > _size || index < 0) {
            return;
        }
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    // 删去第index个节点，假如index 大于等于链表的长度，直接return，留意index是从0开端的
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        _size--;
    }
    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;

python完成的双链表代码：

# 双链表
# 相对于单链表, Node新增了prev属性
class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None
class MyLinkedList:
    def __init__(self):
        self._head, self._tail = Node(0), Node(0)  # 虚拟节点
        self._head.next, self._tail.prev = self._tail, self._head
        self._count = 0  # 增加的节点数
    def _get_node(self, index: int) -> Node:
        # 当index小于_count//2时, 运用_head查找更快, 反之_tail更快
        if index >= self._count // 2:
            # 运用prev往前找
            node = self._tail
            for _ in range(self._count - index):
                node = node.prev
        else:
            # 运用next往后找
            node = self._head   
            for _ in range(index + 1):
                node = node.next
        return node
    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 0 <= index < self._count:
            node = self._get_node(index)
            return node.val
        else:
            return -1
    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._update(self._head, self._head.next, val)
    def addAtTail(self, val: int) -> None:
        """
        Append a node of value val to the last element of the linked list.
        """
        self._update(self._tail.prev, self._tail, 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 < 0:
            index = 0
        elif index > self._count:
            return
        node = self._get_node(index)
        self._update(node.prev, node, val)
    def _update(self, prev: Node, next: Node, val: int) -> None:
        """
            更新节点
            :param prev: 相对于更新的前一个节点
            :param next: 相对于更新的后一个节点
            :param val:  要增加的节点值
        """
        # 计数累加
        self._count += 1
        node = Node(val)
        prev.next, next.prev = node, node
        node.prev, node.next = prev, next
    def deleteAtIndex(self, index: int) -> None:
        """
        Delete the index-th node in the linked list, if the index is valid.
        """
        if 0 <= index < self._count:
            node = self._get_node(index)
            # 计数-1
            self._count -= 1
            node.prev.next, node.next.prev = node.next, node.prev

206. 回转链表

标题链接：leetcode.cn/problems/re…

本题的关键在于不开辟新的内存空间，完成回转。即，每次指针滑动对应修改节点的next指针走向。

具体完成办法：双指针 使用pre和cur指针，完成回转。留意：pred指向的是虚拟头节点，这是由于头节点回转之后，->next = nullptr，使用while完成，停止条件为cur == nullptr。

c++完成的双指针代码为：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，由于接下来要改动cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

此题，能够用递归法改写内部的while句子。

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 能够和双指针法的代码进行比照，如下递归的写法，其实便是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, 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 reverseList(self, head: ListNode) -> ListNode:
        cur = head   
        pre = None
        while(cur!=None):
            temp = cur.next # 保存一下 cur的下一个节点，由于接下来要改动cur->next
            cur.next = pre #回转
            #更新pre、cur指针
            pre = cur
            cur = temp
        return pre
# 递归法
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def reverse(pre,cur):
            if not cur:
                return pre
            tmp = cur.next
            cur.next = pre
            return reverse(cur,tmp)
        return reverse(None,head)

24. 两两交换链表中的节点

标题链接：leetcode.cn/problems/sw…

第一次做的时分用的是python，一开端写的比较复杂，后来看了参阅代码，用了3个节点: pre,cur,post别离代表前中后三个节点方位。但本题用c++写会比用python写逻辑更清楚一些。

python参阅代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        res = ListNode(next=head)
        pre = res
        # 必须有pre的下一个和下下个才干交换，否则阐明现已交换结束了
        while pre.next and pre.next.next:
            cur = pre.next
            post = pre.next.next
            # pre，cur，post对应最左，中心的，最右边的节点
            cur.next = post.next
            post.next = cur
            pre.next = post
            pre = pre.next.next
        return res.next

c++参阅代码：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后边做删去操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记载暂时节点
            ListNode* tmp1 = cur->next->next->next; // 记载暂时节点
            cur->next = cur->next->next;    // 进程一
            cur->next->next = tmp;          // 进程二
            cur->next->next->next = tmp1;   // 进程三
            cur = cur->next->next; // cur移动两位，准备下一轮交换
        }
        return dummyHead->next;
    }
};

19. 删去链表的倒数第N个节点

标题链接：leetcode.cn/problems/re…

这道题是独立用c++写出来的第一题，思路略有承认，可是画图承认的移动进程和参阅解析根本一致。

这是一题经典的双指针应用题，使用slow和fast的错位移动定位到要操作的两个节点上。

c++参阅代码：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next; // fast再提前走一步，由于需求让slow指向删去节点的上一个节点
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummyHead->next;
    }
};

面试题02.07 链表相交

标题链接：leetcode.cn/problems/in…

这道题的解题关键在于：先找到两个链表的长度差，然后再同步移动。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾方位对齐）
        while (gap--) {
            curA = curA->next;
        }
        // 遍历curA 和 curB，遇到相同则直接回来
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};
  • 时刻复杂度: O(m+n)
  • 空间复杂度: O(1)

142. 环形链表II

标题链接：leetcode.cn/problems/li…

此题难度较高，采用的办法是：快慢指针法，别离界说fast和slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，假如fast和slow指针在途中相遇，阐明这个链表有环。 但是确认两者入环的节点需求一些数学推导，能够参阅卡哥的详细推导，需求多看几遍。

参阅卡哥的解说，提交的c++代码如下，本题需求在while循环中在满足条件的情况下return。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 难题，第一次做，需求用到一些推导
        // 此处的快慢指针是快指针每次移动2个节点，慢指针每次移动1个节点；
        // 这个标题在推导进程中用的等式是不能用虚拟头指针做的；假如用了虚拟头指针，公式就不成立了；
        // 所以对只有一个节点的问题，需求独自评论
        ListNode* slow;
        ListNode* quick;
        // cout << head << endl;
        quick = head;
        slow = head;
        // 这个标题 我出错的原因在于不会在while中return 
        while (quick != NULL && quick->next != NULL){ // 还有一个可能是quick->next是NULL
            quick = quick->next->next; //快指针每次走两个节点
            slow = slow->next; // 慢指针每次走一个节点
            if (quick == slow){ //也便是当两者相遇时
            // 根据画图后的公式推导，在相遇点生成一个index1，并从head开端走一个index2,两个指针每次都只走一步，直到两者相遇;
            // x = (n-1)(y+z)+z
                ListNode* index1 = quick; 
                ListNode* index2 = head;
                while (index1 != index2){
                    index1 = index1->next;
                    index2 = index2->next;
                    cout << index1->val << " " << index2->val << endl;
        }
            return index1; // 若index1 和index2指针相遇，当时节点便是环的进口
            }
        } // 只要快指针不会抵达NULL指针，这就阐明有个闭环，否则，就直接回来NULL
        return NULL; // 没有闭环
    }
};