技术图文：双指针在链表问题中的应用

75 阅读 0 评论 50 点赞

我是靠谱客的博主辛勤雪糕，最近开发中收集的这篇文章主要介绍技术图文：双指针在链表问题中的应用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

背景

最近这段时间团队在进行算法刻意练习活动，我带着同学们刷 leetcode 的“腾讯精选练习（50）题”，参见：我是如何组织“算法刻意练习活动”的？

在做题的过程中，同学们讨论比较多的是链表中遇到的问题，我在这里为大家总结一下，双指针在链表问题中的应用。

技术分析

第一个问题：删除链表中的第N个节点

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

做这个题目的思路就是，利用两个指针，开始时都指向头结点，先让一个指针顺着链表移动 N 个节点，然后两个指针同时移动，当前面的指针移动到 null 时，后面的指针就指向需要删除的节点位置。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution
{
    public ListNode RemoveNthFormEnd(ListNode head, int n)
    {
        ListNode temp1 = head;
        ListNode temp2 = head;
        int len = 0;
        int index = 0;
        while (temp1 != null)
        {
            temp1 = temp1.next;
            len++;
            if (index == n)
            {
                break;
            }
            index++;
        }

        if (len == n)
        {
            head = head.next;
            return head;
        }

        while (temp1 != null)
        {
            temp1 = temp1.next;
            temp2 = temp2.next;
        }

        temp2.next = temp2.next.next;
        return head;
    }
}

第二个问题：对单链表中的元素进行排序

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3

输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0

输出: -1->0->3->4->5

如果待排的元素存储在数组中，就是我们的并归排序了。而这些元素存储在链表中，我们无法直接利用并归排序，只能借鉴并归排序的思想对算法进行修改。

并归排序的思想是将待排序列进行分组，直到包含一个元素为止，然后回溯合并两个有序序列，最后得到排序序列。

对于链表我们可以使用双指针的方式对链表节点进行分组。第一个指针每次移动两个节点，另一个指针每次移动一个节点，当前面的指针移动到 null 时，后面的指针刚好移动到中间位置，这样我们就可以根据中间节点将链表分成两个部分，即完成了对节点的分组。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */

public class Solution
{
    public ListNode SortList(ListNode head)
    {
        if (head == null)
            return null;
        return MergeSort(head);

    }

    private ListNode MergeSort(ListNode node)
    {
        if (node.next == null)
        {
            return node;
        }
        ListNode fast = node;
        ListNode slow = node;
        ListNode cut = null;
        while (fast != null && fast.next != null)
        {
            cut = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        cut.next = null;
        ListNode l1 = MergeSort(node);
        ListNode l2 = MergeSort(slow);
        return MergeTwoLists(l1, l2);
    }

    private ListNode MergeTwoLists(ListNode l1, ListNode l2)
    {
        ListNode pHead = new ListNode(int.MaxValue);
        ListNode temp = pHead;

        while (l1 != null && l2 != null)
        {
            if (l1.val < l2.val)
            {
                temp.next = l1;
                l1 = l1.next;
            }
            else
            {
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }

        if (l1 != null)
            temp.next = l1;

        if (l2 != null)
            temp.next = l2;

        return pHead.next;
    }
}

第三个问题：判断单链表是否为循环链表

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：true

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0

输出：true

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1

输出：false

解释：链表中没有环。

通常情况下，判断是否包含了重复的元素，我们使用 Hash 的方式来做。对于单链表的这种场景，我们也可以使用双指针的方式。

第一个指针每次移动两个节点，第二个指针每次移动一个节点，如果该链表存在环的话，第一个指针一定会再次碰到第二个指针，反之，则不存在环。

比如：head = [1,2,3,4,5]

第一个指针：1 3 5 2 4 1

第二个指针：1 2 3 4 5 1

代码如下：

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

        while (fast != null && fast.next != null)
        {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow)
                return true;
        }
        return false;
    }
}