【程序员代码面试指南】三 链表问题

在单链表和双链表中删除倒数第k个节点

分别实现两个函数,一个可以删除单链表中倒数第k个节点,另一个可以删除双链表中倒数第k个节点。

要求: 如果链表长度为N,时间复杂度达到O(N),额外空间复杂度达到O(1)。

步骤:

从链表头开始遍历链表,每走一步,k自加-1

遍历完单链表时,查看k的情况:

1
2
3
4
5
6
7
8
9
k = k - 1;
if k == 0 then
return head;
else if k > 0 then
-- 说明k的大小大于length
return null;
else if k < 0 then
-- ...
end
  • 如果k等于0,那么当然k等于链表的长度,倒数第k个也就是第0个,直接返回链表头即可。
  • 如果k大于0,说明遍历完了链表,还不能把k消除干净,也就是k大于链表长度,倒数第k个是不存在的

接下来考虑k小于0的情况。

接下来我们演绎推理一波:

  1. 当从头把链表遍历到尾时,此时的k为k = orignalK - len
  2. 倒数第k个数,其实就是正数第len - originalK个数
  3. 所以:此时的k的负数,也就是-k,就是欲删除节点的正向下标

由于删除单链表节点的时候,需要的是欲删除节点的上一个节点,所以我们要把-k值乘以-1后减去1,得到欲删除的节点的上一个节点的正向下标。

1
local preIndex = -k - 1;

接下来只要再次遍历到这个节点,处理删除就好了。

删除链表的中间结点

给一个链表的头结点head,实现删除链表中间结点的函数。
例如:
head为null时,不删除任何结点;
1->2,删除节点1
1->2->3 删除节点2
1->2->3->4 删除节点2
1->2->3->4->5 删除节点

最蠢方法

遍历一次链表得到其长度,除以二得到中间结点位置,再次遍历链表,删除中间结点。

分析

首先我们要找规律。可以发现,当链表长度小于等于2时,删除的规律比较特殊:

  • 若为空链表,那么直接返回空链表
  • 若链表长度为1,那么返回head
  • 若链表长度为2,那么返回第二个节点,也就是head.next

从链表长度为3开始,仔细观察可以发现,链表长度每每增加二,那么欲删除节点就要往右移动一位(两个等差数列)。

核心思想

首先针对长度小于等于2的情况,做特殊处理。

再来处理有三个节点或以上的情形。初始化pre节点为head节点,cur节点为第三个节点。开始一个while循环来遍历链表,cur节点代表当前遍历到的链表长度,每次增加两步,pre代表中间结点的前一个节点,每次增加一步。当cur移动到链表末端的时候,停止循环,此时的pre就是中间结点的前一个节点。

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
public class Node
{
public int Value;
public Node Next;

public Node(int data)
{
Value = data;
}

public static Node RemoveMidNode(Node head)
{
// 处理链表长度小于等于1的情况,直接返回head
if(head == null || head.Next == null)
{
return head;
}
// 处理链表长度为2的情况,直接返回第二个节点
if(head.Next.Next == null)
{
return head.Next;
}
// 初始化pre节点和cur节点
Node pre = head;
Node cur = head.Next.Next;
while(cur.Next != null && cur.Next.Next != null)
{
// 前置节点每次只走一步
pre = pre.Next;
// 长度节点每次走两步
cur = cur.Next.Next;
}
// 重新链接节点
pre.Next = pre.Next.Next;
return head;
}
}

倒序一个单向链表

给定一个单向链表的头head,要求逆序这个链表。

愚蠢想法及其错误之处

最愚蠢的想法就是把链表当做数组看,想要以中间结点为轴来镜像调换链表内容。

这是因为没有了解到链表的实质只是一堆数据+指向。链表的数据在什么位置,我们根本不用关心,逆序链表,只需要逆序指向就够了。

智者的思路

所谓逆序链表,提取规律之后可以发现,其实就需要修改两个部分:

  1. 把原链表的最后一个节点变成head
  2. 把所有的节点指示方向调转

如:

1
2
3
4
5
6
7
8
// 原链表
head

1 -> 2 -> 3 -> 4
// 逆序后
head

1 <- 2 <- 3 <- 4

当然,按照前面几道题的思路来看,这两步是可以用一次循环来完成的。

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
public class Node
[
public Node next;
int value;
public Node(int value)
{
value = value;
}

public static Node reverseList(Node head)
{
Node pre = null;
Node next = null;
Node cur = head;
while(cur != null) {
// 1. 先缓存当前的下一个节点到next
next = cur.next;
// 2. 很自然地,把当前节点指向前一个节点
cur.next = pre;
// 3. 移动上一个节点到当前(也就是移动一位)
pre = cur;
// 4. 当前节点往后移一位,由于原本链表的下一位已经被next缓存起来,所以直接用next赋值
cur = next;
}
// 5. 最后返回的是pre,为最后一个节点,cur已经是null了
return pre;
}
]

判断单链表是否为回文结构

解法一

原理:

  1. 栈是先进后出的。
  2. 回文结构就是把链表倒过来倒过去,都是相等的

使用栈进行逆序,一一比较。

遍历第一遍,把所有的节点加入到某个空栈中,然后遍历一次链表,同时一一出栈节点,进行两两比较。

解法二

原理:

  1. 栈是先进后出的
  2. 回文结构意味着链表是沿中间结点对称的

这次只需要遍历一次。入栈一半的节点,然后一一出栈,和链表的后半段做比较。

如何知道中间结点在哪里?这要参考上面的删除链表的中间结点。弄两个指针,一个一次走两步,一个一次走一步,等第一个指针走到末的时候,第二个指针就停留在中间结点的位置。这次做个小改进,第二个节点在走的时候,顺便把节点的内容入栈。

解法三

原理:

从链表的头和尾分别往中间结点方向遍历,比较两个节点是否相等。首先要反转链表的后半部分,然后分别从头结点和尾结点往中间遍历。

步骤:

  1. 首先把head赋值给leftStart
  2. 启用两个节点,一次遍历,使其中一个节点走到中间结点middle,一个走到尾结点。把尾结点赋值给rightStart。
  3. 从中间结点往rightStart遍历,并调转每个节点的next方向,以反转后半部分的链表
  4. 开始一个循环,分别从leftStart和rightStart开始遍历链表,并逐一比较取得的节点
  5. 恢复反转链表

这里涉及了上面题目提到的两个重要技术:

  1. 寻找中间结点
  2. 反转链表

根据一个pivot,将链表分为三部分

给定一个pivot的值,要求将链表分为小于pivot,等于pivot,大于pivot的排序。

这也太简单了,直接比较,生成三个链表,最后串起来就好。

复制含有随机指针节点的链表

这个链表的节点有点特殊,节点里除了有next的数据以外,还有一个指向另一个节点的的引用rand:

1
2
3
4
5
6
7
8
9
10
public class Node {
public int value;
public Node next;
public Node rand;

public Node(int value)
{
value = value;
}
}

写出一个函数来复制这个链表。

叨叨几句

复制普通的链表简单,难在如何给rand赋值。我们的思路就是,当检测到某个rand的值的时候,要能够知道rand'的值,这就要保证有两次的循环,以保证第二次循环的时候所有的rand'应指向的节点都被创建。

第一种解法

第一种解法就是利用我们上面提到的原理做的。

  1. 遍历第一遍原链表,复制出另一个链表,但是 不复制 nextrand字段。在第一次遍历链表的过程中,我们每复制完一个节点,就往一个哈希表HashMap<Node, Node>中添加一个键值对,其中,key是原节点node,value是复制节点node'
  2. 第二次遍历原链表。遍历中,每次都根据node作为key在哈希表中找到对应的节点,然后以nextrand为key再找到对应的nextrand节点。找到对应的nextrand键值对之后,他们的value其实就是next'rand'了,我们把他们的值复制给node'nextrand

由于Java很麻烦,我自己写一个lua版本的吧。

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
local Node = class("Node");
Node.value = nil;
Node.next = nil;
Node.rand = nil;
function Node.Create(value)
local self = Node.ctor();
self.value = value;
end

function Node.DeepCopy(Node head)
local hashTable = {};
local cur = head;
-- 对应第一步
while cur.next ~= nil do
local nodeCopy = Node.Create(value);
hashTable[cur] = nodeCopy;
cur = cur.next;
end
-- 对应第二步
cur = head;
while cur.next ~= nil do
local nodeCopy = hashTable[cur];
local nextCopy = hashTable[cur.next];
local randCopy = hashTable[cur.rand];
nodeCopy.next = nextCopy;
nodeCopy.rand = randCopy;
end
-- 返回新的头结点
return hashTable[head];
end

额外空间复杂度$O(n)$,时间复杂度$O(n)$。

第二种解法

  1. 遍历一次链表并复制节点,把nodeCopy放到node后面,把nodeCopynext变成node.next,让nodenext变成nodeCopy。比如1 -> 2 ->3 ->4 变成了1 -> 1’ -> 2 -> 2’ -> 3 -> 3’ -> 4 -> 4’。
  2. 第二次遍历从头开始遍历。取下1rand存起来,然后把1'next指向1'.next.next,再把1'rand指向1.rand.next
  3. 分离两个链表

本质上和第一种解法是一样的,就是第二次遍历的时候根据原链表节点找到的rand和next,要能够很方便的找到对应的rand’和next’。第一种解法是用键值对来匹配,第二种解法由于已经确定了每个rand节点的下一个节点就是rand’,每个next的下一个节点就是next’,也能够实现找到对应节点的需求,所以也是可以的。

解题的关键就是第二次遍历的时候要知道怎么找到rand和next所对应的rand’和next’。

两个链表相加生成相加链表

给定两个链表,它们从头到尾分别表示一个数字,把它们加起来,然后得到另一个链表。

比如1-2-3-4-5 + 1-2-3-4-5得到链表2-4-6-9-0

最简单的解法就是调转两个链表,然后从头开始相加,当需要进一位的时候就往下一个节点的计算加一。最后把结果链表和两个加数链表调转回来。

两个链表相交的一系列问题

(略过)

将单链表的每k个节点之间逆序

若最后不够k个节点一组,则不逆序。

自己先想一个思路吧。

  1. 把大链表按照k分成多个子链表,这个是避免不了的
  2. 用嵌套循环就行了,还是大小指针的思路,大指针先走k步然后停住,确保了这个子链表的长度有k之后,说明这个子链表需要被逆序。(需求里说了不够k个节点就不逆序)
  3. 保存当前子链表的头结点为tail(作为逆序后的最后一个节点),逆序当前子链表,保存新的头结点head。将上一个逆序的子链表的尾节点的next指向当前子链表的头结点
  4. 重复以上过程
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
public class Node
{
public Node Next;
public Int32 Value;

public Node(Int32 value)
{
Value = value;
}

public static Node ReverseByKStep(Node head, Int32 k)
{
Node pSmall = head;
Node pBig = head;
Node newHead = null;
Node newChildHead = head;
Node newChildTail = null;
while(pBig != null)
{
Bool shouldInverse = true;
for(Int32 step = 0; step < k; step++)
{
if(pBig == null)
{
// 子链表不够k个,不用逆序
shouldInverse = false;
break;
}
pBig = pBig.Next;
}
// 如果需要逆序,就逆序
if(shouldInverse)
{
Node childTail = pSmall;
while(pSmall.Next != pBig)
{
// 调转相邻两个节点之间的方向,并返回新的后面那个节点(节点会往后移动一步)
pSmall = InverseDirection(pSmall, pSmall.Next);
}
newChildHead = pSmall;
if(newChildTail)
{
newChildTail.Next = newChildHead;
}
newChildTail = childTail;
}
else
{
if(newChildTail)
{
newChildTail.Next = pSmall;
}
}
// 只赋值一次,相当于处理第一个子链表的时候把新子链表的头赋值过来
if(newHead == null)
{
newHead = newChildHead;
}
}
return newHead;
}
}

删除无序链表中值重复出现的节点

给一个链表头head,删除其中值重复出现的点。

首先我们前面做了这么多题,要明确一个点:想要删除一个节点,我们得先知道它的前置节点。

想知道一个值是否重复出现,那我们就 存储和统计 它的前置节点就好了。

为此,一个 哈希表 是必不可少的。

我们的哈希表是这样设计的:

  1. 哈希表的key是链表节点的值
  2. 哈希表的值是一个 数组 ,数组内容是key的值对应节点的前置节点

假设我们有一个链表: 1, 1, 2, 3, 7, 8, 7
那么遍历完这个链表可以得到哈希表:

1
2
3
4
5
1 => [null, node0]
2 => [node1]
3 => [node2]
7 => [node3, node5]
8 => [node4]

接下来我们遍历这个哈希表,只要是发现value的数组的长度大于1,就代表这个数值的节点个数大于1,重复了,需要被删除。然后我们遍历这个数组,把里面的节点的下一个节点删除:

  1. 当值为null时,代表要删除的下一个节点是node0
  2. 其余的情况,直接删除下一个节点,然后重整链表(把前置节点的next连接到下下个节点)
  3. 由于进入数组的是前置节点,所以不会出现没有下一个节点的情况

最终把所有的重复节点删除。

Buy Me A Coffee / 捐一杯咖啡的钱
分享这篇文章~
0%
//