LeetCode-Hot100-链表

2026-03-16
作者 lin
~8.33K 字

1. 160.相交链表 cpp
2. 206.反转链表 cpp
3. 234.回文链表 cpp
4. 141.环形链表 cpp
5. 142.环形链表II cpp
6. 21.合并两个有序链表 cpp
7. 2.两数相加 cpp

160.相交链表 cpp

具体算法如下：

初始化两个指针 p = headA，q = headB。
不断循环，直到 p = q。
每次循环，p和q各向后走一步。具体来说:
如果p不是空节点（即p=p为真），那么更新p为p.next，否则更新p为headB；
如果q不是空节点（即q=q为真），那么更新q为q.next，否则更新q为headA。
循环结束时，如果两条链表相交，那么此时p和q都在相交的起始节点处，返回p；如果两条链表不相交，那么p和q都走到空节点，所以也可以返回p，即空节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p = headA;
        ListNode* q = headB;
        while (p != q){
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        return p;
    }
};

206.反转链表 cpp

头插法，从头往后遍历，每一个结点插到前面即完成反转
nxt: 下一趟要插的结点 nxt = cur->next
cur: 当前处理的结点，初始为head
pre: cur要指向的结点，初始为 nullptr

/**
 * 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* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

234.回文链表 cpp

找到中间结点，从中间结点反转链表，即得到尾结点，从头结点和尾结点同时遍历，判断回文(一定要用val判断，判断的是 值相同，不是是否为同一个结点)。

/**
 * 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 {
    ListNode* midNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
public:
    bool isPalindrome(ListNode* head) {
        ListNode* mid = midNode(head);
        ListNode* head2 = reverseList(mid);
        while(head2) {
            if (head->val != head2->val)
                return false;
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};

141.环形链表 cpp

快慢指针，龟兔赛跑的思想。如果快慢指针相遇，说明有环，否则无环。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
};

142.环形链表II cpp

Floyd判圈算法：
设头节点到入环口需要走a步。设环长为c。
设相遇的时候，慢指针走了b步，那么快指针走了2b步。
设快指针比慢指针多走了k圈，即2b-b=kc，得b=kc。
慢指针从入环口开始，在环中走了b-a= kc—a步到达相遇点。
这说明从相遇点开始，再走a步，就恰好走到入环口了!虽然不知道a是多少，但如果让头节点和慢指针同时走，恰好a步后二者必定相遇，且相遇点就在入环口。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow) {
                while(slow != head) {
                    slow = slow->next;
                    head = head->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

21.合并两个有序链表 cpp

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy;
        ListNode* cur = &dummy;
        while(list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next;
            } else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2;
        return dummy.next;
    }
};

Q：ListNode 和 ListNode* 的区别是什么？

A：

一句话总结

ListNode：是节点本身（实实在在的结构体对象）
ListNode*：是指向节点的指针（存的是地址，不是对象）

详细对比

ListNode

就是你定义的那个结构体类型：

struct ListNode {
    int val;
    ListNode *next;
};

它是值类型
定义时会真的分配内存
存的是：val + next 指针

1	ListNode node; // 直接创建一个节点对象

ListNode*

是指向 ListNode 的指针，本质是个地址。

1	ListNode* p;

它不存节点，只存节点在内存里的地址
本身不创造节点，只是指向别人
用来遍历链表、修改链表、串联节点

最关键的区别（链表必懂）

你写：

1 2	ListNode a; ListNode b = a;

这是拷贝，两个完全独立的对象，互不影响。

你写：

1 2	ListNode a; ListNode* p = &a;

p 只是指向 a
通过 p->val 改的就是 a 的 val

放在你这道题里看

1	ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)

这里传的是 ListNode*
意思是：传链表头节点的地址
不是把整个链表拷贝一份
你在函数里改的就是原链表

1	ListNode* p = list1;

p 是一个指针
它从头开始遍历链表
不是复制节点，只是移动指针

超简记忆口诀

ListNode = 房子本身
ListNode* = 房子的地址 / 门牌号

你要串联链表，必须用指针（门牌号），不能用对象本身。

Q：为什么cur移动了，而初始为空的dummy.next变成了头结点？

A：
dummy.next 最开始确实是 nullptr，是在循环里被“改成”头结点的。

刚创建时：dummy.next 是 nullptr

1	ListNode dummy;

用的是默认构造：

1	ListNode() : val(0), next(nullptr) {}

所以一开始是：

dummy.val = 0
dummy.next = nullptr

1	dummy: [0 \| nullptr]

cur 一开始指向 dummy

1	ListNode* cur = &dummy;

1
2
3

dummy: [0 | nullptr]
         ↑
       cur

第一次进循环：dummy.next 变成头结点！

假设：

list1 = 1 -> 2 -> …
list2 = 3 -> 4 -> …

第一次循环：

1	cur->next = list1;

这里的 cur 现在还是指向 dummy，
所以 cur->next 就是 dummy.next

这句话等价于：

1	dummy.next = list1;

瞬间变成：

1
2
3

dummy: [0 | next] ------> list1（1节点）
         ↑
       cur

就在这一行，dummy.next 从 nullptr 变成了真正的头结点！

然后 cur 才往后走，不影响 dummy

1	cur = cur->next;

现在：

1
2
3

dummy: [0 | next] ------> 1（头结点） ------> 2 ...
                                 ↑
                               cur

dummy 一动不动
dummy.next 永远是头
cur 往后跑了

dummy.next 什么时候变成头结点的？

第一次执行 cur->next = list1 或 cur->next = list2 时。
因为那时 cur 还指向 dummy，所以改的就是 dummy.next。

一开始不是没给赋初始值吗？

一开始确实是 nullptr，
是在循环第一句被赋值成头结点的，不是一开始就有。

最精髓的一句话

dummy 自己从来不动，只在第一次赋值时，把它的 next 指向了链表第一个节点，之后 cur 怎么跑都跟 dummy 没关系了。

2.两数相加 cpp

递归
c保存进位
原地修改l1，保证l1是长的，否则交换l1和l2。
l1和l2都为空时，还有进位就用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* addTwoNumbers(ListNode* l1, ListNode* l2, int c = 0) {
        if (l1 == nullptr && l2 == nullptr) 
            return c ? new ListNode(c) : nullptr;
        if (l1 == nullptr) swap(l1,l2);
        int sum = c + l1->val + (l2 ? l2->val : 0);
        l1->val = sum % 10;
        l1->next = addTwoNumbers(l1->next, (l2 ? l2->next : nullptr), sum / 10);
        return l1;
    }
};

Hexo

LeetCode-Hot100-链表

160.相交链表 cpp

206.反转链表 cpp

234.回文链表 cpp

141.环形链表 cpp

142.环形链表II cpp

21.合并两个有序链表 cpp

2.两数相加 cpp

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

Hexo

160.相交链表 cpp

206.反转链表 cpp

234.回文链表 cpp

141.环形链表 cpp

142.环形链表II cpp

21.合并两个有序链表 cpp

2.两数相加 cpp

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可