寻找链表的中间节点

利用快慢指针，开始两个指针都指向头，快指针每次前进两步，慢指针每次前进一步。快指针达到终点时，慢指针刚好达到中点。

/// <summary>
/// 寻找链表的中间节点
/// https://leetcode.cn/problems/middle-of-the-linked-list/description/
/// </summary>
public static ListNode MiddleNode(ListNode head)
{
    if (head == null || head.next == null) return head;

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

    return new ListNode(slow.val);
}

倒数第n个节点

倒数第N个节点的查找与删除。同样是利用快慢指针，先让快指针先走N步，然后快慢指针同时向前走，直到快指针达到终点，此时慢指针指向倒数第N个节点。

/// <summary>
/// 查找倒数第n个节点
/// </summary>
public static ListNode TrainingPlan(ListNode head, int cnt)
{
    if (head == null || head.next == null) return head;

    ListNode virsualNode = new ListNode(int.MinValue);
    virsualNode.next = head;

    ListNode fast = virsualNode;
    ListNode tail = virsualNode;
    while (fast != null && cnt > 0)
    {
        fast = fast.next;
        --cnt;
    }
    if (fast == null) return null;

    while (fast.next != null)
    {
        fast = fast.next;
        tail = tail.next;
    }

    return tail.next;
}

/// <summary>
/// 移除倒数第n个节点
/// https://leetcode.cn/problems/SLwz0R/description/
/// </summary>
public static ListNode RemoveNthFromEnd(ListNode head, int n)
{
    if (head == null) return head;

    ListNode virsualNode = new ListNode(int.MinValue);
    virsualNode.next = head;

    ListNode fast = virsualNode;
    ListNode tail = virsualNode;
    while (fast != null && n > 0)
    {
        fast = fast.next;
        --n;
    }
    if (fast == null) return null;

    while (fast.next != null)
    {
        fast = fast.next;
        tail = tail.next;
    }
    tail.next = tail.next.next;

    return virsualNode.next;
}

合并有序链表

合并两个链表很简单，精华在下面合并N个有序链表

/// <summary>
/// 合并两个有序链表
/// https://leetcode.cn/problems/merge-two-sorted-lists/
/// </summary>
public static ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
    if (l1 == null) return l2;
    if (l2 == null) return l1;

    ListNode virsualNode = new ListNode(int.MinValue);
    ListNode result = virsualNode;
    while (l1 != null && l2 != null)
    {
        if (l1.val <= l2.val)
        {
            virsualNode.next = l1;
            l1 = l1.next;
        }
        else
        {
            virsualNode.next = l2;
            l2 = l2.next;
        }
        virsualNode = virsualNode.next;
    }
    if (l1 == null) virsualNode.next = l2;
    else virsualNode.next = l1;

    return result.next;
}

/// <summary>
/// 合并N个升序链表
/// https://leetcode.cn/problems/merge-k-sorted-lists/description/
/// </summary>
public static ListNode MergeKLists(ListNode[] lists)
{
    ListNode start = new ListNode(int.MinValue);
    ListNode result = start;

    int nullCount = 0;
    while (nullCount < lists.Length)
    {
        nullCount = 0;

        int minIndex = -1;
        int minValue = int.MaxValue;
        for (int i = 0; i < lists.Length; i++)
        {
            if (lists[i] == null) { ++nullCount; continue; }

            if (lists[i].val <= minValue)
            {
                minValue = lists[i].val;
                minIndex = i;
            }
        }
        if (minIndex == -1) break;

        start.next = lists[minIndex];
        lists[minIndex] = lists[minIndex].next;
        start = start.next;
    }

    return result.next;
}

两个链表是否相交

画个图好理解：

将两个链表分别连接下对方，如下：

此时两个链表长度相同。然后两个链表都开始向尾部移动，如果两个指针相同就说明是共公节点。如果链表遍历结束没有出现相同节点，则说明两个链表没有公共节点。

/// <summary>
/// 两个链表的第一个公共节点
/// https://leetcode.cn/problems/3u1WK4/description/
/// </summary>
public static ListNode GetIntersectionNode(ListNode headA, ListNode headB)
{
    ListNode AA = headA;
    ListNode BB = headB;
    while (AA != BB)
    {
        AA = AA != null ? AA.next : headB;
        BB = BB != null ? BB.next : headA;
    }
    return AA;
}

链表是否包含环

是否有环，同样快慢指针

快指针每次向前两步，慢指针每次向前一步，

如果这个链表有环：快指针会与慢指针重合
遍历到结尾也没重合，说明没有环。

找到环的起点

利用上面方式找到相同节点后。我们知道快指针走过的距离是慢指针的2倍，假设快指针走了2k,慢指针走了k，那么环的大小就是k。

将快/慢指针任意一个回到头节点。
然后两个只能都每次走1步。
两个指针相交时就是环的开始节点。

/// <summary>
/// 链表是否包含环
/// https://leetcode.cn/problems/linked-list-cycle/description/
/// </summary>
public static bool HasCycle(ListNode head)
{
    if (head == null || head.next == null) return false;

    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;
}

/// <summary>
/// 返回环形链表的第一个节点
/// https://leetcode.cn/problems/linked-list-cycle-ii/description/
/// </summary>
public static ListNode DetectCycle(ListNode head)
{
    ListNode fast = head;
    ListNode slow = head;

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

        if (fast == slow) break;
    }
    if (fast == null || fast.next == null) return null;

    fast = head;
    while (fast != slow)
    {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}

赏

支付宝

微信

关闭

算法-链表专题