theme: juejin highlight: github

链表全攻略

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

在这里实现了用c++实现算法不报错的第一步，并尝试利用日志输出c++代码的中间过程来寻找代码问题。

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

链表理论基础

链表扫盲

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

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

链表定义图

上图描述的即为单链表，该类链表每个节点只有一个指向的指针。 c++实现的单链表结构体： c++ // 单链表 struct ListNode{ int val; // 节点上存储的元素 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数 }; // 最后面的这个分号不要忘记 其实c++会默认生成一个构造函数，但是这个构造函数会无法直接在初始化的时候给变量赋值。 ```c++ // 使用自己写的构造函数，初始化节点 ListNode* head = new ListNode(5); // 一个新的链表需要新开辟一个内存空间

// 使用默认的构造函数，初始化节点； ListNode* head = new ListNode(); head->val = 5; ```

此处，补充python的链表类： python class ListNode: def __init__(self, val, next=None): self.val = val self.next = next

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

链表节点在内存中的分配图

链表操作

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

删除节点步骤

添加节点 链表的添加和删除都是O(1)操作，不会影响到其他节点，但是需要花O(n)的时间复杂度，搜索指定位置的节点，因为节点总是从头开始查找的，利用next指针进行删除操作。

添加节点步骤

与数组的比较

|| 插入/删除（时间复杂度） | 查询（时间复杂度）|适用场景| |--------------| ------ | ----- | --------| |数组|O(n)|O(1)|数据量固定，频繁查询，较少增删| |链表|O(1)|O(n)|数据量不固定，频繁增删，较少查询|

其他链表类型

双链表

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

双链表

循环链表

首尾相连的链表

循环链表

Leetcode相关题目及解法要义

203. 移除链表元素

题目链接： http://leetcode.cn/problems/remove-linked-list-elements/

此题是虚拟头节点的入门题，虚拟头节点的使用一般是为了避免链表对头节点的单独处理。最后返回的头节点是return dummyHead->next;

虚拟头节点的入门题

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

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使用虚拟头节点的思路（可以不用手动释放删除的节点内存）： ```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. 设计链表

题目链接：http://leetcode.cn/problems/design-linked-list/

此题共涉及了链表的五个接口 - 获取链表第index个节点的数值； - 在链表的最前面插入一个节点； - 在链表的最后面插入一个节点； - 在链表第index个节点前面插入一个节点； - 删除链表的第index个节点。

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

c++实现的单链表操作代码： ```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实现的双链表代码：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. 反转链表

题目链接：http://leetcode.cn/problems/reverse-linked-list/

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

具体实现方法：双指针 利用pre和cur指针，实现反转。注意：pred指向的是虚拟头节点，这是因为头节点反转之后，->next = nullptr，利用while实现，终止条件为cur == nullptr。

c++实现的双指针代码为： 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语句。 ```c++ 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实现的代码：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. 两两交换链表中的节点

题目链接：http://leetcode.cn/problems/swap-nodes-in-pairs/

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

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++参考代码： ```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个节点

题目链接：http://leetcode.cn/problems/remove-nth-node-from-end-of-list/

这道题是独立用c++写出来的第一题，思路略有确认，但是画图确认的移动过程和参考解析基本一致。

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

c++参考代码： 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 链表相交

题目链接：http://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

这道题的解题关键在于：先找到两个链表的长度差，然后再同步移动。 c++ 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

题目链接：http://leetcode.cn/problems/linked-list-cycle-ii/

🌟🌟🌟此题难度较高，采用的方法是：快慢指针法，分别定义fast和slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果fast和slow指针在途中相遇，说明这个链表有环。然而确定两者入环的节点需要一些数学推导，可以参考卡哥的详细推导，需要多看几遍。

参考卡哥的解释，提交的c++代码如下，本题需要在while循环中在满足条件的情况下return。 ``` c++ 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; // 没有闭环

}

}; ```

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

链表全攻略

链表理论基础

链表扫盲

链表操作

与数组的比较

其他链表类型

Leetcode相关题目及解法要义

203. 移除链表元素

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

707. 设计链表

双链表

相对于单链表, Node新增了prev属性

206. 反转链表

双指针

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

递归法

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

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

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

面试题02.07 链表相交

142. 环形链表II