如何判断回文链表 :: labuladong的算法小抄

[labuladong]

文章链接点这里：如何判断回文链表

评论礼仪 见这里，违者直接拉黑。

[jswxwxf]

js 递归后序遍历版

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

function buildLinkList(values) {
  return values.reverse().reduce((acc, val) => new ListNode(val, acc), null);
}

// ---- Generate our linked list ----
const linkedList = buildLinkList(["a"]);

var isPalindrome = function (head) {
  // 左侧指针
  let left = head;
  return traverse(head);
  function traverse(right) {
    if (right === null) return true;
    let res = traverse(right.next);
    // 后序遍历代码
    res = res && right.val === left.val;
    left = left.next;
    return res;
  }
};

console.log(isPalindrome(linkedList));

[jswxwxf]

js 双指针版

function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

function buildLinkList(values) {
  return values.reverse().reduce((acc, val) => new ListNode(val, acc), null);
}

// ---- Generate our linked list ----
const linkedList = buildLinkList(["a", "b", "b", "a"]);

var isPalindrome = function (head) {
  if (head === null || head.next === null) return head;

  let slow = head,
    fast = head;
  // 寻找链表中点
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // 如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步：
  if (fast !== null) {
    slow = slow.next;
  }
  // slow 指针现在指向链表中点

  // 从slow开始反转后面的链表
  let left = head,
    right = reverse(slow);
  let p = null,
    q = right;
  // 比较回文串
  while (right !== null) {
    if (left.val !== right.val) return false;
    p = left;
    left = left.next;
    right = right.next;
  }

  // 恢复原先链表顺序
  p.next = reverse(q);
  return true;

  function reverse(head) {
    let prev = null,
      cur = head;
    while (cur != null) {
      const next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
    }
    return prev;
  }
};

console.log(isPalindrome(linkedList));

[clearlovel7]

python 双指针版

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow,fast=head,head
        while fast!=None and fast.next!=None:
            slow=slow.next
            fast=fast.next.next

        pre,cur=None,slow
        while cur!=None:
            nxt= cur.next
            cur.next=pre
            pre=cur
            cur=nxt

        while pre!=None:
            if pre.val!=head.val:
                return False
            pre=pre.next
            head=head.next
        return True

[clearlovel7]

python 递归版

class Solution:
    def __init__(self):
        self.left=None

    def traverse(self,right):
        if right==None:
            return True
        res=self.traverse(right.next)
        res=res and (right.val==self.left.val)
        self.left=self.left.next
        return res

    def isPalindrome(self, head: ListNode) -> bool:
        self.left=head
        return self.traverse(head)

[Alwin4Zhang]

是不是也可以通过将中点左侧或者右侧的链表翻转，然后双指针分别从头遍历2个链表判断是不是相同链表？

[beta-yu]

Go

func isPalindrome(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	if fast != nil { // 奇数个节点
		slow = slow.Next
	}

	left := head
	right := reverseListNodes(slow)
	for right != nil {
		if left.Val != right.Val {
			return false
		}
		left = left.Next
		right = right.Next
	}
	return true
}

func reverseListNodes(head *ListNode) *ListNode {
	var pre, next *ListNode
	cur := head
	for cur != nil {
		next = cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

[1302304703]

这里的reverse使用前边的递归反转实现

public boolean isPalindrome(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步
        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 static 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;
    }

[Yzxsysu]

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode pre, cur, nxt;
        pre = null;
        cur = nxt = head;
        while (cur != null){
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        while (pre != null && head != null){
            if (pre.val != head.val) return false;
            pre = pre.next;
            head = head.next;
        }
        return true;
    }
}

我的思路是先把链表反过来，然后再遍历pre和head对比值如果存在不同的话就返回false
反之则返回true，但是[1,1,2,1]输入通过不了，而[1,2,2,1]可以通过

[zhangyi20000]

我也是这样[1,1,2,1]通过不了

[2176700277]

原链表已经被破坏，你又没有恢复原链表

[shiboys]

重新再翻转下，这个你自己不能完成？

[cheng-miao]

daka

[alsomilo]

文章末尾提到的恢复原链表顺序，我觉得不需要知道p的位置。因为之前翻转链表后半部分时，并没有修改到图中的p.next，而是修改到了slow.next（变成了NULL）。所以恢复时只需要做 reverse(q)即可复原， p.next = reverse(q)没必要做。q的位置可以在回文比对修改right前备份q=right

[lzwanan]

打卡

[cxu2]

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

这一步判断奇偶其实不用也可以吧， 1 -> 2 -> 3 -> 2 -> 1的情况，第一个2的next始终指向3，就算slow从3开始reverse, 最后比较的也是head: 1 -> 2 -> 3 -> null 和 reverse(slow): 1 -> 2 -> 3 -> null

[fantian007]

起始可以把整个链表的值放入一个数组，然后判断是否回文数组也可以

function isPalindrome(head: ListNode | null): boolean {
  if (head === null || head.next === null) {
    return true;
  }

  const arr = [];

  let cur = head;

  while (cur !== null) {
    arr.push(cur.val);

    cur = cur.next;
  }

  while (arr.length) {
    if (arr.length === 1) {
      return true;
    }

    const left = arr.shift();
    const right = arr.pop();

    if (left !== right) {
      return false;
    }
  }

  return true;
};

[rickycaron]

C++ 后序遍历版

    ListNode* left;
    bool postOrderTraversal(ListNode* head)
    {
        if(head == nullptr)
            return true;
        bool res = postOrderTraversal(head->next);
        res = res && (left->val == head->val);
        left = left->next;
        return res;
    }
    bool isPalindrome(ListNode* head) 
    {
        left = head;
        return postOrderTraversal(head);
    }

[supercoko]

leetcode 上我用数组先存储一下的方法为什么 空间和时间都优于递归都方法啊?

[yezire]

递归本来性能就不优，只是说用递归写出来的代码很简洁优美

[yezire]

打卡d4

[Ainnoce]

c++ 翻转链表版本

    bool isPalindrome(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while(fast->next!=nullptr && fast->next->next!=nullptr){
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode *right = slow->next;
    ListNode *left = head;
    right = reverse(right);
    while(right != nullptr){
        if(right->val != left->val) {
            slow->next = reverse(right);
            return false;
        }
        left = left->next;
        right = right->next;
    }
    slow->next = reverse(right);
    return true;
    }

    ListNode* reverse(ListNode* left){
        ListNode *pre = nullptr, *cur = left;
        while(cur != nullptr){
            ListNode *next_ = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next_;
        }
        return pre;
    }

[Ainnoce]

isPalindrome()的缩进没整好，不知道怎么删除。。。

[Bittttter]

感觉可以不用反转链表，
先找到 slow，
从 slow 开始继续往后，递归的“后序”中和 head 做比较直到递归结束。

[Ainnoce]

嗯嗯，这也是一种思路，我写翻转是因为文章中提到了，为了让内存占用最小；如果从slow往后递归，内存占用应该介于全链表递归和翻转之间，时间复杂度应该会小一些，感谢提醒~

[PvP-zzz]

这种解法虽然高效，但破坏了输入链表的原始结构，能不能避免这个瑕疵呢

[labuladong]

你可以创建一个新的链表操作

[Loomione]

翻转链表那里，让slow多走一步(slow = slow->next)完全是多此一举了。当链表个数为奇数时，使用快慢指针找到的就刚好是链表的中间结点，例如：

1->2->3->4->5;
找到中间结点3；
翻转后半部分，得到：
1->2->3<-4<-5;

while (right != nullptr) {
        if (left->val != right->val)
            return false;
        left = left->next;
        right = right->next;
    }

在这部分代码中最后就相当于判断了3==3，所以slow=slow->next完全没必要。

[labuladong]

明白你的意思了，感谢指出，这一步确实不必要

[CarlLy7]

打卡

//破坏原始链表结构的Java代码
    private ListNode reverse(ListNode head){
        ListNode pre,cur,next;
        pre=null;
        cur=next=head;
        while(next!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }

    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) {
            //如果上面的循环中是因为fast.next==null退出的，说明这个链表个数是一个奇数
            //这里的反转的起点还要后移一位
            slow = slow.next;
        }
        //反转后面的链表
        ListNode newHead = reverse(slow);
        ListNode left = head;
        ListNode right = newHead;
        while (right != null) {
            if(left.val!=right.val){
                return false;
            }
            left=left.next;
            right=right.next;
        }
        return true;
    }
//没有破坏原始链表结构的Java代码
    private ListNode reverse(ListNode head){
        ListNode pre,cur,next;
        pre=null;
        cur=next=head;
        while(next!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
public boolean isPalindrome(ListNode head) {
    //定义快慢指针来找到链表的中点
    ListNode slow, fast;
    slow = fast = head;
    ListNode p=new ListNode();
    while (fast != null && fast.next != null) {
        p.next=slow;
        p=p.next;
        slow = slow.next;
        fast = fast.next.next;
    }
    if (fast != null) {
        //如果上面的循环中是因为fast.next==null退出的，说明这个链表个数是一个奇数
        //这里的反转的起点还要后移一位
        p=slow;
        slow = slow.next;
    }
    //反转后面的链表
    ListNode newHead = reverse(slow);
    ListNode left = head;
    ListNode right = newHead;
    while (right != null) {
        if(left.val!=right.val){
            return false;
        }
        left=left.next;
        right=right.next;
    }
    p.next=reverse(newHead);
    return true;
}

[wqy71]

快慢指针找中间节点那里，可以创建一个新的头节点NullNode.next指向head，fast,slow = NullNode,NullNode；这样找到的中间节点mid的下一个节点mid.next可以直接拿来reverse，省去了第二步判断链表长度奇偶的代码。只额外使用了一个ListNode的空间，空间复杂度还是O(1)。

[forexgg]

python 递归的写法，如果不用global的变量left，也可以采用nonlocal的写法，这样就不改变leetcode题目的结构

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        left = head

        def traverse(head):
            nonlocal left
            if head is None:
                return True
            res = traverse(head.next) 
            res = res and (head.val == left.val)
            left = left.next
            return res

        return traverse(head)

[yexia553]

打卡

[JeanYang2]

python 双指针版

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseLink(self,head):
        pre,cur=None,head
        while cur:
            nxt=cur.next
            cur.next=pre
            pre=cur
            cur=nxt
        return pre

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow,fast=head,head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        if fast:
            slow=slow.next
        left,right=head,self.reverseLink(slow)
        while right:
            if left.val!=right.val:
                return False
            left=left.next
            right=right.next
        return True

[gaoqs-github]

好奇，能不能使用这个思路去判断一个二叉树是否对称

[shiboys]

碉堡了！真的，链表玩出了新高度！

[yuren1978]

学习了。

[Davidmxg]

问东哥 图是用啥软件画的？