侧边栏壁纸
博主头像
996worker

祇園精舎の鐘の聲, 諸行無常の響き有り。

  • 累计撰写 174 篇文章
  • 累计创建 45 个标签
  • 累计收到 8 条评论

目 录CONTENT

文章目录

发现一个寻找链表中点的方法--快慢指针

996worker
2021-07-31 / 0 评论 / 0 点赞 / 161 阅读 / 1,486 字
温馨提示:
本文最后更新于 2021-08-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

起因

因为链表不能随机访问,所以不太好找中点。今天有一个方法能够找到链表中点。有了终点后,能够解决点实际问题,比如判断回文链表.

经过

直接看代码

ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// 此时。。。

我们来看此时的情况

  • 当快指针fast非空,慢指针slow指向的就是中节点。
  • 当快指针fast空,慢指针slow + 1指向中节点。

为什么?
画图:
IMG_CB0E70E584EE1.jpeg

道理很简单,快指针速度是慢指针的2倍。

有啥用?

今有一题:

请判断一个链表是否为回文链表。

示例 1:
输入: 1->2
输出: false

示例 2:
输入: 1->2->2->1
输出: true

对于此题,可以先找到链表中点:

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

if (fast != null) {
    slow = slow.next;
}

// slow为中点

接下来,把slow中点后的反转,反转可以用递归.该递归思路见另一博文:

public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

用这反转函数反转slow后的list,然后对比左右两部分:

ListNode left = head;
ListNode right = reverse(slow);

while (right != null) {
    if (left.val != right.val)
        return false;
    left = left.next;
    right = right.next;
}
return true;

合并下:

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

        if (fast != null) slow = slow.next;
        
        ListNode left = head;
        ListNode right = reverse(slow);

        while (right != null) {
            if (left.val != right.val)
                return false;
            left = left.next;
            right = right.next;
        }

        return true;
    }

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

这方法有个缺点,就是会打乱输入的链表结构,解决方案:
维持两个指针pq,令pslow之前一个节点,q在最后一个节点,然后在主函数return前添加:

p.next = reverse(q);
0

评论区