剑指offer刷题3——链表2(简单)

剑指 Offer 24. 反转链表

难度 简单

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制:

1
0 <= 节点个数 <= 5000

1.迭代(双指针)

考虑遍历链表,并在访问各节点时修改 next 引用指向,算法流程见注释。

复杂度分析: 时间复杂度 O(N)O(N) : 遍历链表使用线性大小时间。 空间复杂度 O(1)O(1) : 变量 pre 和 cur 使用常数大小额外空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 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 *cur,*pre,*tmp;
pre = NULL;
cur = head;
while(pre)
{
tmp = cur->next; // 暂存后继节点 cur.next
cur->next = pre; // 修改 next 引用指向
pre = cur; // pre 暂存 cur
cur = tmp; // cur 访问下一节点
}
return pre;
}
};

2.递归

考虑使用递归法遍历链表,当越过尾节点后终止递归,在回溯时修改各节点的 next 引用指向。

recur(cur, pre)递归函数: 终止条件:当 cur 为空,则返回尾节点 pre (即反转链表的头节点); 递归后继节点,记录返回值(即反转链表的头节点)为 res ; 修改当前节点 cur 引用指向前驱节点 pre ; 返回反转链表的头节点 res ; reverseList(head) 函数: 调用并返回 recur(head, null) 。传入 null 是因为反转链表后, head 节点指向 null ;

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
ListNode* reverseList(ListNode* head) {
return recur(head, nullptr); // 调用递归并返回
}
private:
ListNode* recur(ListNode* cur, ListNode* pre) {
if (cur == nullptr) return pre; // 终止条件
ListNode* res = recur(cur->next, cur); // 递归后继节点
cur->next = pre; // 修改节点引用指向
return res; // 返回反转链表的头节点
}
};

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

难度 中等

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null

示例 1:

img

1
2
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:

img

1
2
输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]

示例 3:

img

1
2
输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

示例 4:

1
2
3
输入:head = []
输出:[]
解释:给定的链表为空(空指针),因此返回 null。

提示:

  • -10000 <= Node.val <= 10000
  • Node.random 为空(null)或指向链表中的节点。
  • 节点数目不超过 1000 。

注意:本题与主站 138 题相同:https://leetcode-cn.com/problems/copy-list-with-random-pointer/

迭代+结点拆分

第一次遍历:在链表各节点中间插入新的节点,复制节点的值

第二次遍历:复制链表各节点的random指向

第三次遍历:分离链表,将两个链表之间的next关系分离形成两个链表

代码

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
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return head;
Node *headNew, *cur, *Pre;
Pre = head;
while(Pre != NULL)
{
cur = (Node*)malloc(sizeof(Node));
cur->val = Pre->val;
cur->next = Pre->next;
Pre->next = cur;
Pre = Pre->next->next;
}
cur = head;
while(cur)
{
if(cur->random!=NULL) cur->next->random = cur->random->next;
else cur->next->random = NULL;
cur = cur->next->next;
}
headNew = head->next;cur = head->next;Pre = head;
while(Pre)
{
Pre->next = cur->next;
Pre = Pre->next;
if(cur->next!=NULL) cur->next = Pre->next;
cur = cur->next;
}
return headNew;
}
};