LeetCode + 《剑指Offer II》刷题笔记。
链表
单向链表
定义
1
2
3
4
5
6
7
8
|
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
|
链表插入
1
2
3
4
5
6
7
8
9
10
11
|
public ListNode append(ListNode head, int value) {
ListNode newNode = new ListNode(value);
if (head == null) return newNode;
ListNode node = head;
while (node.next != null) {
node = node.next;
}
node.next = newNode;
return head;
}
|
链表删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public ListNode delete(ListNode head, int value) {
if (head == null) return head;
if (head.val == value) return head.next;
ListNode node = head;
while (node.next != null) {
if (node.next.val == value) {
node.next = node.next.next;
break;
}
node = node.next;
}
return head;
}
|
哨兵节点
哨兵节点是为了简化处理链表边界条件而引入的附加链表节点。哨兵节点通常位于链表的头部，它的值没有任何意义。在一个有哨兵节点的链表中，从第2个节点开始才真正保存有意义的信息。
用哨兵节点简化链表插入操作
首先创建一个哨兵节点，并把该节点当作链表的头节点，然后把原始的链表添加在哨兵节点的后面。当完成添加操作之后，再返回链表真正的头节点，也就是哨兵节点的下一个节点。
1
2
3
4
5
6
7
8
9
10
11
12
|
public ListNode append(ListNode head, int value) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode newNode = new ListNode(value);
ListNode node = dummy;
while (node.next != null) {
node = node.next;
}
node.next = newNode;
return dummy.next;
}
|
由于将新创建的一个哨兵节点当作链表的头节点，链表无论如何也不会为空，因此不需要使用if语句来单独处理输入头节点head为null的情形。哨兵节点简化了代码的逻辑。
用哨兵节点简化链表删除操作
前面链表删除的代码中有两条if语句，分别用于处理两个特殊情况：
如果在链表的最前面添加一个哨兵节点作为头节点，那么链表就不为空，并且链表的头节点无论如何都不会被删除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public ListNode delete(ListNode head, int value) {
ListNode dummy=new ListNode(0);
dummy.next=head;
if (head.val == value) return head.next;
ListNode node = dummy;
while (node.next != null) {
if (node.next.val == value) {
node.next = node.next.next;
break;
}
node = node.next;
}
return dummy.next;
}
|
使用哨兵节点可以简化创建或删除链表头节点操作的代码。
双指针
前后双指针
前后双指针：即一个指针在链表中提前朝着指向下一个节点的指针移动若干步，然后移动第2个指针。
前后双指针的经典应用是查找链表的倒数第k个节点。先让第1个指针从链表的头节点开始朝着指向下一个节点的指针先移动k-1步，然后让第2个指针指向链表的头节点，再让两个指针以相同的速度一起移动，当第1个指针到达链表的尾节点时第2个指针正好指向倒数第k个节点。
19 Remove Nth Node From End of List
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyNode=new ListNode(0);
dummyNode->next=head;
ListNode* slow=dummyNode;
ListNode* fast=dummyNode;
while(n-- && fast){
fast=fast->next;
}
// fast再往前走一步，因为需要让slow指向删除节点的上一个节点
fast=fast->next;
while(slow && fast){
slow=slow->next;
fast=fast->next;
}
slow->next=slow->next->next;
return dummyNode->next;
}
};
|
- 时间复杂度：O(N)，其中 N 是给定链表的结点数目。
- 空间复杂度：O(1)。
遍历计算长度
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
|
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
int sz=0;
ListNode* start=head;
while(start){
sz++;
start=start->next;
}
// cout << sz << endl;
int i=0;
ListNode* dummyNode=new ListNode(0);
dummyNode->next=head;
ListNode* node=dummyNode;
while(node){
if(i==sz-n){
node->next=node->next->next;
break;
}
node=node->next;
i++;
}
return dummyNode->next;
}
};
|
- 时间复杂度：O(N)，其中 N 是给定链表的结点数目。
- 空间复杂度：O(1)。
栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyNode=new ListNode(0);
dummyNode->next=head;
stack<ListNode*> stk;
ListNode* start=dummyNode;
while(start){
stk.push(start);
start=start->next;
}
for(int i=0;i<n;i++){
stk.pop();
}
ListNode* node=stk.top();
node->next=node->next->next;
return dummyNode->next;
}
};
|
- 时间复杂度：O(N)，其中 N 是给定链表的结点数目。
- 空间复杂度：O(N)。
快慢双指针
快慢双指针：即两个指针在链表中移动的速度不一样，通常是快的指针朝着指向下一个节点的指针一次移动两步，慢的指针一次只移动一步。采用这种方法，在一个没有环的链表中，当快的指针到达链表尾节点的时候慢的指针正好指向链表的中间节点。
876 Middle of the Linked List
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* fast=head;
ListNode* slow=head;
while(fast && fast->next){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
};
|
- 时间复杂度：O(N)，其中 N 是给定链表的结点数目。
- 空间复杂度：O(1)。
这个Easy题自己都没有一次Accepted！
注意while循环中的循环条件：fast && fast->next
如果题目要求：「两个中间结点的时候，返回第二个中间结点」，此时快指针可以前进的条件是：当前快指针和当前快指针的下一个结点都非空。
如果题目要求「在两个中间结点的时候，返回第一个中间结点」，此时快指针可以前进的条件是：当前快指针的下一个结点和当前快指针的下下一个结点都非空。
快慢指针的前进方向相同，且它们步伐的「差」是恒定的。
ELSE
Key Point: 如果两个链表相交，那么相交点之后的长度是相同的。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA || !headB) return nullptr;
ListNode *pa=headA,*pb=headB;
while(pa!=pb){
pa= pa==nullptr?headB:pa->next;
pb= pb==nullptr?headA:pb->next;
}
return pa;
}
};
|
- 时间复杂度 O(a + b)
- 空间复杂度 O(1)
206 Reverse Linked List
iterative
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre=nullptr,*cur=head;
while(cur){
ListNode *rear=cur->next;
cur->next=pre;
pre=cur;
cur=rear;
}
return pre;
}
};
|
recursive
1
2
3
4
5
6
7
8
9
10
|
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr || head->next==nullptr) return head;
ListNode* newHead=reverseList(head->next);
head->next->next=head;
head->next=nullptr;
return newHead;
}
};
|
143 Reorder List
方法一：线性表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
void reorderList(ListNode* head) {
if(head==nullptr) return;
vector<ListNode*> v;
ListNode* cur=head;
while(cur){
v.push_back(cur);
cur=cur->next;
}
int i=0,j=v.size()-1;
while(i<j){
v[i]->next=v[j];
i++;
if(i==j) break;
v[j]->next=v[i];
j--;
}
v[i]->next=nullptr;
}
};
|
方法二：寻找链表中点 + 链表逆序 + 合并链表
注意到目标链表为将原链表的左半端和反转后的右半端合并后的结果。
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
|
class Solution {
public:
ListNode* middleNode(ListNode* head){
ListNode *fast=head,*slow=head;
while(fast->next && fast->next->next){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
ListNode* reverseList(ListNode* head){
ListNode *prev=nullptr,*cur=head;
while(cur){
ListNode* rear=cur->next;
cur->next=prev;
prev=cur;
cur=rear;
}
return prev;
}
void mergeList(ListNode* front,ListNode* rear){
ListNode* front_next;
ListNode* rear_next;
while(front && rear){
ListNode* front_next=front->next;
ListNode* rear_next=rear->next;
front->next=rear;
front=front_next;
rear->next=front;
rear=rear_next;
}
}
void reorderList(ListNode* head) {
if(head==nullptr) return;
ListNode *front=head;
ListNode *middle=middleNode(head);
ListNode *rear=middle->next;
middle->next=nullptr;
rear=reverseList(rear);
mergeList(front,rear);
}
};
|
注意1：求中间结点时，返回第一个 or 第二个中间结点都是对的。
所以
1
2
3
|
while(fast->next && fast->next->next){
...
}
|
和
1
2
3
|
while(fast && fast->next){
...
}
|
都是可以的。
注意2：这里求反转后的右半端时的处理方法，比反转链表多一些处理。
1
2
3
|
ListNode *rear=middle->next;
middle->next=nullptr;
rear=reverseList(rear);
|
237 Delete Node in a Linked List
1
2
3
4
5
6
7
8
|
class Solution {
public:
void deleteNode(ListNode* node) {
//swap with next node
node->val=node->next->val;
node->next=node->next->next;
}
};
|
2 Add Two Numbers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *dummynode=new ListNode(0);
ListNode *cur=dummynode;
int carry=0;
while(l1 || l2){
int a=l1?l1->val:0;
int b=l2?l2->val:0;
int sum=a+b+carry;
ListNode *node=new ListNode(sum%10);
cur->next=node;
cur=cur->next;
carry=sum/10;
if(l1) l1=l1->next;
if(l2) l2=l2->next;
}
if(carry!=0){
cur->next=new ListNode(carry);
}
return dummynode->next;
}
};
|
- 时间复杂度 O(max(m,n))
- 空间复杂度 O(1)
Author
Anjana
LastMod
2022-01-28
License
原创文章，如需转载请注明作者和出处。谢谢！