如何判断回文链表 :: 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]可以通过

[2176700277]

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

[cheng-miao]

daka

[alsomilo]

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

[Sm1lence]

打卡

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

[bert82503]

打卡，感谢楼主！

[GeorgeSmith215]

// TS快慢指针翻转还原版
function findMid(head: ListNode | null): ListNode {
  let fast = head, slow = head
  while (fast !== null && fast.next !== null) {
    fast = fast.next.next
    slow = slow.next
  }
  return slow
}

function reverse(head: ListNode | null): ListNode {
  let pre = null, cur = head, nxt = null
  while (cur !== null) {
    nxt = cur.next
    cur.next = pre
    pre = cur
    cur = nxt
  }
  return pre
}

function isPalindrome(head: ListNode | null): boolean {
  let pre = head, post = reverse(findMid(head)), q = post
  while (post !== null) {
    if (post.val === pre.val) {
      post = post.next
      pre = pre.next
    }
    else return false
  }
  // 还原原链表
  pre = reverse(q)
  if (post === null) return true
  return false
};

[GeorgeSmith215]

// TS后序遍历版
let left:ListNode
function isPalindrome(head: ListNode | null): boolean {
  left = head
  return traverse(head)
};

function traverse(right: ListNode | null): boolean {
  if (right === null) return true
  let res = traverse(right.next)
  res = res && (right.val === left.val)
  left = left.next
  return res
}

[deepbreath373]

check in

[Maxiah]

东哥，请问一下开头说的两篇文章（写了回文串和回文序列相关的问题）在哪里呀，在左侧栏和数组那篇都搜索了没搜到

[labuladong]

@Maxiah 已更新链接

[LeeHaruYa]

滴滴滴打卡

[weifpeng]

function isPalindrome(head: ListNode | null): boolean {
    const dummy=new ListNode(-1)
    dummy.next=head

    let fast=dummy;
    let slow=dummy;
    while(fast?.next){
        fast=fast.next?.next
        slow=slow.next
    }

    // 反转 slow
    let curr=slow.next
    let prev=slow
    while(curr){
        const next=curr.next
        curr.next=prev
        prev=curr
        curr=next
    }

    slow.next=null

    let left=head,right=prev
    while(left){
        if(left?.val!==right?.val) return false
        left=left.next
        right=right?.next
    }

    return true
};