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

发表于 | 分类于 | 阅读次数:

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

由于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后面，把nodeCopy的next变成node.next，让node的next变成nodeCopy。比如1 -> 2 ->3 ->4 变成了1 -> 1’ -> 2 -> 2’ -> 3 -> 3’ -> 4 -> 4’。
  2. 第二次遍历从头开始遍历。取下1的rand存起来，然后把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%
//