Leetcode. 链表

记住这些:

  1. 虚头结点&双指针就能解决大部分问题

  2. 舍得用变量,千万别想着节省变量,否则容易被逻辑绕晕

  3. head 有可能需要改动时,先增加一个 假head,返回的时候直接取 假head.next,这样就不需要为修改 head 增加一大堆逻辑了。往往这种时候,cur指针先指在dummynode,然后循环中使用cur>next与cur->next->next,来进行遍历

  4. 画出遍历、移动等过程


题目

剑指 Offer 06. 从尾到头打印链表

剑指 Offer 18. 删除链表的节点

剑指 Offer 22. 链表中倒数第k个节点

剑指 Offer 24. 反转链表

剑指 Offer 25. 合并两个排序的链表

剑指 Offer 35. 复杂链表的复制

剑指 Offer 36. 二叉搜索树与双向链表

剑指 Offer 52. 两个链表的第一个公共节点

补充

虚头结点&双指针感觉就能解决大部分问题

1
2
3
ListNode* dummyHead = new ListNode(0);   //设置一个虚拟头结点
dummyHead->next = head; //将虚拟头结点指向head,这样方面后面做操作
ListNode* cur = dummyHead; //当前操作节点从虚头节点开始

链表的基本操作

  1. 获取链表第index个节点的数值
  2. 在链表的最前面插入一个节点
  3. 在链表的最后面插入一个节点
  4. 在链表第index个节点前面插入一个节点
  5. 删除链表的第index个节点的数值

力扣 707. 设计链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

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大于链表的长度,则返回空
void addAtIndex(int index, int val) {
if (index > _size) {
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;
};

反转链表(递归、迭代)

力扣 206. 反转链表

删除倒数第N个节点

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

链表相交

力扣 面试题 02.07. 链表相交

环形链表

力扣 142. 环形链表II

1.判断链表是否有环

快慢指针法,分别定义 fast 和 slow 指针,从头结点出发,fast 指针每次移动两个节点,slow 指针每次移动一个节点,如果 fast 和 slow 指针在途中相遇,说明这个链表有环。

2.查找环的入口位置

快慢指针,当第一次相遇时,快指针回到头节点,然后改为一次移动一个节点,下次相遇时的节点就是环入口节点

经典操作

链表的题通常需要注意两点:

  1. 舍得用变量,千万别想着节省变量,否则容易被逻辑绕晕

  2. head 有可能需要改动时,先增加一个 假head,返回的时候直接取 假head.next,这样就不需要为修改 head 增加一大堆逻辑了。

往往这种时候,cur指针先指在dummynode,然后循环中使用cur>next与cur->next->next,来进行遍历

可用作复杂题解的一部分

链表反转

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* head) {
ListNode *pre = head;
ListNode *cur = nullptr;
while(pre) {
ListNode *tmp = pre->next;
pre->next = cur;
cur = pre;
pre = tmp;
}
return cur;
}

链表中间节点

1
2
3
4
5
6
7
8
9
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}

合并升序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummyhead = new ListNode();
ListNode *cur = dummyhead;
while(l1 != nullptr && l2 != nullptr) {
if(l1->val <= l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 == nullptr ? l2 : l1;

return dummyhead->next;
}

删除倒数第N个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* removeNthFromEnd(ListNode* head, int n) {

if(head == nullptr) return nullptr;

ListNode *dummyNode = new ListNode(0,head);
ListNode *slow = dummyNode;
ListNode *fast = head;
int i = n;
while (i > 0) {
fast = fast->next;
i--;
}

while(fast) {
fast = fast->next;
slow = slow->next;
}

slow->next = slow->next->next;
return dummyNode->next;
}

两个链表是否相交?返回相交的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

if(headA == NULL || headB == NULL) return NULL;

ListNode *pa = headA;
ListNode *pb = headB;

while (pa != pb) {

pa = pa == NULL ? headB : pa->next;
pb = pb == NULL ? headA : pb->next;
}
return pa;
}

删除链表元素为a的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* removeElements(ListNode* head, int val) {
ListNode *dummyNode = new ListNode(0, head);

ListNode *pre = dummyNode;
ListNode *cur = head;

while(cur != nullptr) {
if(cur->val == val) {
pre->next = cur->next;
} else {
pre = pre->next;
}
cur = cur->next;
}
return dummyNode->next;
}
文章作者: ゴウサク
文章链接: http://dapaner.top/2021/07/03/Leetcode. 链表/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Corner&Coder
微信赞赏码
支付宝赞赏码