单链表

单链表中的每个结点不仅包含值,还包含链接到下一个结点的引用字段。通过这种方式,单链表将所有结点按顺序组织起来。

下面是一个单链表的例子:
singleLinkedList.png

与数组不同,我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素,我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间,其中 N 是链表的长度。

添加节点

如果我们想在给定的结点 prev 之后添加新值,我们应该:

  1. 使用给定值初始化新结点 cur
    singleLinkedListAdd1.png
  2. curnext 字段链接到 prev 的下一个结点 next
    singleLinkedListAdd2.png
  3. prev 中的 next 字段链接到 cur
    singleLinkedListAdd3.png

我们使用头结点来代表整个列表。因此,在列表开头添加新节点时更新头结点 head 至关重要。
在开头添加结点,我们应该:

  1. 初始化一个新结点 cur
  2. 将新结点链接到我们的原始头结点 head
  3. cur 指定为 head

删除节点

如果我们想从单链表中删除现有结点 cur,可以分两步完成:

  1. 找到 cur 的上一个结点 prev 及其下一个结点 next
    singleLinkedListDelete1.png
  2. 接下来链接 prev 到 cur 的下一个节点 next
    singleLinkedListDelete2.png

在我们的第一步中,我们需要找出 prevnext。使用 cur 的参考字段很容易找出 next,但是,我们必须从头结点遍历链表,以找出 prev,它的平均时间是 O(N),其中 N 是链表的长度。因此,删除结点的时间复杂度将是 O(N)。
空间复杂度为 O(1),因为我们只需要常量空间来存储指针。

如果想要删除第一个结点,我们可以简单地将下一个结点分配给 head

链表中的双指针问题

给定一个链表,判断链表中是否有环。

想象一下,有两个速度不同的跑步者。如果他们在直路上行驶,快跑者将首先到达目的地。但是,如果它们在圆形跑道上跑步,那么快跑者如果继续跑步就会追上慢跑者。

这正是我们在链表中使用两个速度不同的指针时会遇到的情况:

  • 如果没有环,快指针将停在链表的末尾。
  • 如果有环,快指针最终将与慢指针相遇。

这两个指针的适当速度应该是多少?

一个安全的选择是每次移动慢指针一步,而移动快指针两步。每一次迭代,快速指针将额外移动一步。如果环的长度为 M,经过 M 次迭代后,快指针肯定会多绕环一周,并赶上慢指针。

用于解决链表中的双指针问题的模板:

// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;           // move slow pointer one step each time
    fast = fast.next.next;      // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem
  1. 在调用 next 字段之前,始终检查节点是否为空。
    获取空节点的下一个节点将导致空指针错误。例如,在我们运行 fast = fast.next.next 之前,需要检查 fast 和 fast.next 不为空。
  2. 仔细定义循环的结束条件。

复杂度分析

空间复杂度分析容易。如果只使用指针,而不使用任何其他额外的空间,那么空间复杂度将是 O(1)。但是,时间复杂度的分析比较困难。为了得到答案,我们需要分析运行循环的次数。

在前面的查找循环示例中,假设我们每次移动较快的指针 2 步,每次移动较慢的指针 1 步。

  • 如果没有循环,快指针需要 N/2 次才能到达链表的末尾,其中 N 是链表的长度。
  • 如果存在循环,则快指针需要 M 次才能赶上慢指针,其中 M 是列表中循环的长度。

显然,M <= N 。所以我们将循环运行 N 次。对于每次循环,我们只需要常量级的时间。因此,该算法的时间复杂度总共为 O(N)。

142. 环形链表 II

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
circularlinkedlist.png

示例 2:
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
circularlinkedlist_test2.png

示例 3:
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
circularlinkedlist_test3.png

提示:

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶:你是否可以使用 O(1) 空间解决此题?

算法:

我们使用两个指针,fast 与 slow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而 fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。

如下图所示,设链表中环外部分的长度为 a。slow 指针进入环后,又走了 b 的距离与 fast 相遇。此时,fast 指针已经走完了环的 n 圈,因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。

根据题意,任意时刻,fast 指针走过的距离都为 slow 指针的 22 倍。因此,我们有
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

有了 a=c+(n-1)(b+c) 的等量关系,我们会发现:从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离。

因此,当发现 slow 与 fast 相遇时,我们再额外使用一个指针 ptr。起始,它指向链表头部;随后,它和 slow 每次向后移动一个位置。最终,它们会在入环点相遇。

142_fig1.png

代码:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

复杂度分析:

  • 时间复杂度:O(N),其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时,slow 指针走过的距离不会超过链表的总长度;随后寻找入环点时,走过的距离也不会超过链表的总长度。因此,总的执行时间为O(N)+O(N)=O(N)。
  • 空间复杂度:O(1)。我们只使用了slow,fast,ptr 三个指针。

19. 删除链表的倒数第 N 个结点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例 1:

remove_ex1.jpg

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

示例 2:

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

示例 3:

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

提示:

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶:你能尝试使用一趟扫描实现吗?

算法:

由于我们需要找到倒数第 n 个节点,因此我们可以使用两个指针first 和 second 同时对链表进行遍历,并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时,second 就恰好处于倒数第 n 个节点。

具体地,初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历,遍历的次数为 n。此时,first 和 second 之间间隔了 n−1 个节点,即 first 比 second 超前了 n 个节点。

在这之后,我们同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾(即 first 为空指针)时,second 恰好指向倒数第 n 个节点。

如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话,删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点,其余的操作步骤不变。这样一来,当 first 遍历到链表的末尾时,second 的下一个节点就是我们需要删除的节点。

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

复杂度分析:

  • 时间复杂度:O(L),其中 L 是链表的长度。
  • 空间复杂度:O(1)。

206. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:
rev1ex1.jpg

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:
rev1ex2.jpg

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

示例 3:

输入:head = []
输出:[]

提示:

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

算法:

首先我们建立一个 dummy 节点,并将 dummynext 指向 head 。每次循环将 head 节点的下一个节点放到 dummy 节点之后,直到 head 到最后一个节点。

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head==null){
            return null;
        }
        
        ListNode dummy = new ListNode(0,head);

        while (head.next!=null){
            ListNode temp2 = head.next;
            ListNode temp3 = dummy.next;
            dummy.next = temp2;
            head.next = temp2.next;
            temp2.next = temp3;
        }
        return dummy.next;
    }
}

复杂度分析:

  • 时间复杂度:在该算法中,每个结点只移动一次。因此,时间复杂度为 O(N),其中 N 是链表的长度。
  • 空间复杂度: 我们只使用常量级的额外空间,所以空间复杂度为 O(1)。

双链表

双链接列表中的结点具有 Value 字段,用于顺序链接结点的 Next 引用字段,还有指向前一个节点的 Prev 引用字段。

DoubleLinkedList.png

添加节点

如果我们想在现有的结点 prev 之后插入一个新的结点 cur,我们可以将此过程分为两个步骤:

  1. 链接 curprevnext,其中 nextprev 原始的下一个节点;
    DoubleLinkedListAdd1.png
  2. cur 重新链接 prevnext
    DoubleLinkedListAdd2.png
    与单链表类似,添加操作的时间和空间复杂度都是 O(1)。

删除节点

如果我们想从双链表中删除一个现有的结点 cur,我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。
DoubleLinkedListDelete.png

小结

单链表和双链表它们在许多操作中是相似的。

  1. 它们都无法在常量时间内随机访问数据。
  2. 它们都能够在 O(1) 时间内在给定结点之后或列表开头添加一个新结点。
  3. 它们都能够在 O(1) 时间内删除第一个结点。

但是删除给定结点(包括最后一个结点)时略有不同。

  • 在单链表中,它无法获取给定结点的前一个结点,因此在删除给定结点之前我们必须花费 O(N) 时间来找出前一结点。
  • 在双链表中,这会更容易,因为我们可以使用“prev”引用字段获取前一个结点。因此我们可以在 O(1) 时间内删除给定结点。

compare.png

如果你需要经常添加或删除结点,链表可能是一个不错的选择。

如果你需要经常按索引访问元素,数组可能是比链表更好的选择。

最后修改:2022 年 12 月 20 日
如果觉得我的文章对你有用,请随意赞赏