实现单链表的逆序
迭代
翻转即将所有节点的next指针指向前驱节点。
由于是单链表，我们在迭代时不能直接找到前驱节点，所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前，不要忘记保存它的后继节点。
空间复杂度分析：遍历时只有3个额外变量，所以额外的空间复杂度是 O(1)。
时间复杂度分析：只遍历一次链表，时间复杂度是 O(n）。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *prev = nullptr;
ListNode *cur = head;
while (cur)
{
ListNode *next = cur->next;
cur->next = prev;
prev = cur, cur = next;
}
return prev;
}
};
递归
首先我们先考虑 reverseList 函数能做什么，它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head->next)，这样我们可以将以head->next为头节点的链表翻转，并得到原链表的尾节点tail，此时head->next是新链表的尾节点，我们令它的next指针指向head，并将head->next指向空即可将整个链表翻转，且新链表的头节点是tail。
空间复杂度分析：总共递归 n 层，系统栈的空间复杂度是 O(n)，所以总共需要额外 O(n)的空间。
时间复杂度分析：链表中每个节点只被遍历一次，所以时间复杂度是 O(n)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *tail = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return tail;
}
};
LeetCode 21. Merge Two Sorted Lists
题目链接：Merge Two Sorted Lists
题解：Merge Two Sorted Lists1
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/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(0);
ListNode *cur = dummy;
while (l1 != NULL && l2 != NULL) {
if (l1 -> val < l2 -> val) {
cur -> next = l1;
l1 = l1 -> next;
}
else {
cur -> next = l2;
l2 = l2 -> next;
}
cur = cur -> next;
}
cur -> next = (l1 != NULL ? l1 : l2);
return dummy -> next;
}
};
给定两个链表，请找它们的交汇点。
题目链接：LeetCode 160. Intersection of Two Linked Lists
题解：题解
方便理解，画了一个图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22/**
* 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, *q = headB;
while (p != q)
{
if (p) p = p->next;
else p = headB;
if (q) q = q->next;
else q = headA;
}
return p;
}
};
给定一个链表，判断是否存在环
题目链接：LeetCode 141. Linked List Cycle
题解：题解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/**
* 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) {
if (!head || !head->next) return 0;
ListNode *first = head, *second = head;
while (first && second)
{
first = first->next;
second = second->next;
if (second) second = second->next;
if (first == second) return true;
}
return false;
}
};
使用插入排序对一个链表排序
题目链接：LeetCode 147. Insertion Sort List
题解：题解1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode *dumy = new ListNode(-1);
while (head) {
ListNode *next = head->next;
ListNode *p = dumy;
while (p->next && p->next->val <= head->val) p = p->next;
head->next = p->next; //头插法
p->next = head;
head = next;
}
return dumy->next;
}
};