给出一个单链表,确定它是否是回文☆☆☆☆

作者 : IT 大叔 本文共1029个字,预计阅读时间需要3分钟 发布时间: 2020-10-13

让我们来看一个例子[1, 1, 2, 1]。首先,设置两个指针,fastslow从头开始。

1 -> 1 -> 2 -> 1 -> null
sf

(1)移动: fast指针移至末尾,并slow移至中间。

1 -> 1 -> 2 -> 1 -> null
          s          f

(2)反向:右半部分反向,slow指针变为第二个头。

1 -> 1    null <- 2 <- 1
h                      s

(3)比较:运行两个指针head,并slow一起进行比较。

1 -> 1    null <- 2 <- 1
     h            s

实现方式:

爪哇

public boolean isPalindrome(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    if (fast != null) { // odd nodes: let right half smaller
        slow = slow.next;
    }
    slow = reverse(slow);
    fast = head;

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

public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

Y

# Note: while comparing the two halves, restore the list to its original 
# state by reversing the first half back.

def isPalindrome(self, head):
    rev = None
    fast = head
    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, head = head, rev, head.next
    tail = head.next if fast else head
    isPali = True
    while rev:
        isPali = isPali and rev.val == tail.val
        head, head.next, rev = rev, head, rev.next
        tail = tail.next
    return isPali
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 给出一个单链表,确定它是否是回文☆☆☆☆

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论