链表相关算法

冷不防 2022-04-22 01:16 287阅读 0赞

**两个有序的链表合并**

**将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 **

**示例：**

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null && l2 == null) {
                return null;
            }
            ListNode node = new ListNode(0);
            ListNode dummy = node;
            while (l1 != null || l2 != null) {
                if (l1 == null) {
                    node.next = l2;
                    break;
                } else if (l2 == null) {
                    node.next = l1;
                    break;
                } else {
                    if (l1.val < l2.val) {
                        node.next = l1;
                        l1 = l1.next;
                    } else {
                        node.next = l2;
                        l2 = l2.next;
                    }
                    node = node.next;
                }
            }//end while
            return dummy.next;
        }
    }

**删除链表倒数第 n 个结点**

**给定一个链表，删除链表的倒数第 *n *个节点，并且返回链表的头结点。**

**示例：**

给定一个链表: 1->2->3->4->5, 和 n = 2.
    
    当删除了倒数第二个节点后，链表变为 1->2->3->5.

**说明：**

给定的 *n* 保证是有效的。

**进阶：**

你能尝试使用一趟扫描实现吗？

方法一：两次遍历算法

**思路**

我们注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第 (L−n+1)(L - n + 1)(L−n+1) 个结点，其中 LLL 是列表的长度。只要我们找到列表的长度 LLL，这个问题就很容易解决。

**算法**

首先我们将添加一个哑结点作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 LLL。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 (L−n)(L - n)(L−n) 个结点那里。我们把第 (L−n)(L - n)(L−n) 个结点的 `next` 指针重新链接至第 (L−n+2)(L - n + 2)(L−n+2) 个结点，完成这个算法。

![Remove the nth element from a list][]

*图 1. 删除列表中的第 L - n + 1 个元素*

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int length  = 0;
        ListNode first = head;
        while (first != null) {
            length++;
            first = first.next;
        }
        length -= n;
        first = dummy;
        while (length > 0) {
            length--;
            first = first.next;
        }
        first.next = first.next.next;
        return dummy.next;
    }

**复杂度分析**

*  时间复杂度：O(L)O(L)O(L)，
    
    该算法对列表进行了两次遍历，首先计算了列表的长度 LLL 其次找到第 (L−n)(L - n)(L−n) 个结点。 操作执行了 2L−n2L-n2L−n 步，时间复杂度为 O(L)O(L)O(L)。
 *  空间复杂度：O(1)O(1)O(1)，
    
    我们只用了常量级的额外空间。

--------------------

方法二：一次遍历算法

**算法**

上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1n+1n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 nnn 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 nnn 个结点。我们重新链接第二个指针所引用的结点的 `next` 指针指向该结点的下下个结点。

![Remove the nth element from a list][Remove the nth element from a list 1]

*图 2. 删除链表的倒数第 N 个元素*

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        // Advances first pointer so that the gap between first and second is n nodes apart
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
        }
        // Move first to the end, maintaining the gap
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }

**复杂度分析**

*  时间复杂度：O(L)O(L)O(L)，
    
    该算法对含有 LLL 个结点的列表进行了一次遍历。因此时间复杂度为 O(L)O(L)O(L)。
 *  空间复杂度：O(1)O(1)O(1)，
    
    我们只用了常量级的额外空间。

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

**进阶：**  
你能否不使用额外空间解决此题？

方法一：哈希表

**思路**

我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表。

**算法**

我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 `null`（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 `true`（即该链表为环形链表）。

public boolean hasCycle(ListNode head) {
        Set<ListNode> nodesSeen = new HashSet<>();
        while (head != null) {
            if (nodesSeen.contains(head)) {
                return true;
            } else {
                nodesSeen.add(head);
            }
            head = head.next;
        }
        return false;
    }

**复杂度分析**

*  时间复杂度：O(n)O(n)O(n)， 对于含有 nnn 个元素的链表，我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1)O(1)O(1) 的时间。
 *  空间复杂度：O(n)O(n)O(n)， 空间取决于添加到哈希表中的元素数目，最多可以添加 nnn 个元素。

--------------------

方法二：双指针

**思路**

想象一下，两名运动员以不同的速度在环形赛道上跑步会发生什么？

**算法**

通过使用具有 **不同速度** 的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)O(1)O(1)。慢指针每次移动一步，而快指针每次移动两步。

如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 `false`。

现在考虑一个环形链表，把慢指针和快指针想象成两个在环形赛道上跑步的运动员（分别称之为慢跑者与快跑者）。而快跑者最终一定会追上慢跑者。这是为什么呢？考虑下面这种情况（记作情况 A） - 假如快跑者只落后慢跑者一步，在下一次迭代中，它们就会分别跑了一步或两步并相遇。

其他情况又会怎样呢？例如，我们没有考虑快跑者在慢跑者之后两步或三步的情况。但其实不难想到，因为在下一次或者下下次迭代后，又会变成上面提到的情况 A。

public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

**复杂度分析**

*  时间复杂度：O(n)O(n)O(n)， 让我们将 nnn 设为链表中结点的总数。为了分析时间复杂度，我们分别考虑下面两种情况。
    
     *  ***链表中不存在环：***  
        快指针将会首先到达尾部，其时间取决于列表的长度，也就是 O(n)O(n)O(n)。
     *  ***链表中存在环：***  
        我们将慢指针的移动过程划分为两个阶段：非环部分与环形部分：
        
        1.  慢指针在走完非环部分阶段后将进入环形部分：此时，快指针已经进入环中 迭代次数=非环部分长度=N\\text\{迭代次数\} = \\text\{非环部分长度\} = N迭代次数=非环部分长度=N
        2.  两个指针都在环形区域中：考虑两个在环形赛道上的运动员 - 快跑者每次移动两步而慢跑者每次只移动一步。其速度的差值为1，因此需要经过 二者之间距离速度差值\\dfrac\{\\text\{二者之间距离\}\}\{\\text\{速度差值\}\}速度差值二者之间距离 次循环后，快跑者可以追上慢跑者。这个距离几乎就是 "环形部分长度 K\\text\{环形部分长度 K\}环形部分长度 K" 且速度差值为 1，我们得出这样的结论 迭代次数=近似于\\text\{迭代次数\} = \\text\{近似于\}迭代次数=近似于 "环形部分长度 K\\text\{环形部分长度 K\}环形部分长度 K".
    
    因此，在最糟糕的情形下，时间复杂度为 O(N+K)O(N+K)O(N+K)，也就是 O(n)O(n)O(n)。
 *  空间复杂度：O(1)O(1)O(1)， 我们只使用了慢指针和快指针两个结点，所以空间复杂度为 O(1)O(1)O(1)。

**反转一个单链表。**

**示例:**

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

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
         public ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            // dummy 保持不动, 不断把新的node insert到 dummy.next
            ListNode dummy = new ListNode(-1);
            while (head != null) {
                ListNode temp = head.next;
                head.next = dummy.next;
                dummy.next = head;
                head = temp;
            }
            return dummy.next;
        }
    }

**给定一个带有头结点 `head` 的非空单链表，返回链表的中间结点。**

**如果有两个中间结点，则返回第二个中间结点。**

**示例 1：**

输入：[1,2,3,4,5]
    输出：此列表中的结点 3 (序列化形式：[3,4,5])
    返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
    注意，我们返回了一个 ListNode 类型的对象 ans，这样：
    ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

**示例 2：**

输入：[1,2,3,4,5,6]
    输出：此列表中的结点 4 (序列化形式：[4,5,6])
    由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

方法一：输出到数组

**思路和算法**

按顺序将每个结点放入数组 `A` 中。然后中间结点就是 `A[A.Length/2]`，因为我们可以通过索引检索每个结点。

class Solution {
        public ListNode middleNode(ListNode head) {
            ListNode[] A = new ListNode[100];
            int t = 0;
            while (head.next != null) {
                A[t++] = head;
                head = head.next;
            }
            return A[t / 2];
        }
    }

**复杂度分析**

*  时间复杂度：O(N)O(N)O(N)，其中 NNN 是给定列表中的结点数目。
 *  空间复杂度：O(N)O(N)O(N)，`A` 用去的空间。

方法二：快慢指针法

**思路和算法**

当用慢指针 `slow` 遍历列表时，让另一个指针 `fast` 的速度是它的两倍。当 `fast` 到达列表的末尾时，`slow` 必然位于中间。

class Solution {
        public ListNode middleNode(ListNode head) {
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }

**复杂度分析**

*  时间复杂度：O(N)O(N)O(N)，其中 NNN 是给定列表的结点数目
 *  空间复杂度：O(1)O(1)O(1)，`slow` 和 `fast` 用去的空间。

[Remove the nth element from a list]: https://leetcode-cn.com/media/original_images/19/19_Remove_nth_node_from_end_of_listA.png
[Remove the nth element from a list 1]: https://leetcode-cn.com/media/original_images/19/19_Remove_nth_node_from_end_of_listB.png