題目描述

https://www.nowcoder.com/practice/baefd05def524a92bcfa6e1f113ed4f0?tpId=8&&tqId=11006&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

請編寫一個函數，檢查鏈表是否為回文。

給定一個鏈表ListNode*?pHead，請返回一個bool，代表鏈表是否為回文。

測試樣例：

{1,2,3,2,1} 返回：true {1,2,3,2,3} 返回：false

?

老樣子還是先掛代碼

import java.util.*;/* public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;} }*/ public class Palindrome {public boolean isPalindrome(ListNode head) { if (head == null) {return false;}if (head.next == null) {return true;}ListNode fp = head;ListNode lp = head;while (fp.next != null && fp.next.next != null) {fp = fp.next.next;lp = lp.next;}ListNode n1 = lp.next;ListNode n2 = n1.next;ListNode n3 = null;lp.next = null;n1.next = null;while (n2 != null) { // 反向鏈接需要三個節點循環n3 = n2.next;n2.next = n1;n1 = n2;n2 = n3;}ListNode tail = n1;while (head != null && tail != null) {if (head.val == tail.val) {head = head.next;tail = tail.next;} else {n2 = n1.next;n1.next = null;while (n2 != null) {n3 = n2.next;n2.next = n1;n1 = n2;n2 = n3;}lp.next = n1;return false;}}n2 = n1.next;n1.next = null;while (n2 != null) {n3 = n2.next;n2.next = n1;n1 = n2;n2 = n3;}lp.next = n1;return true;} }

這個代碼比較長，但是它的額外空間復雜度為O(1)，用最簡單的存儲比較方式的話需要空間復雜度O(N)或者O(N/2)

代碼的原理主要是用一個快指針fp和一個慢指針lp，當fp移動到最后尾部（鏈表為奇數）或者尾部前一個（鏈表為偶數）時，lp會達到左半部分的某位，中間的左邊（鏈表為偶數），或者最中間（鏈表為奇數）

12345677654321對于這個鏈表,fp會停在右2,lp會停在左7

1234567654321,fp會停在最后1，lp會停在7

然后將右邊的鏈表結構改成逆序，生成兩個新的鏈表，尾節點都指向null，分別遍歷比較就好了。

?

下面附上左神算法課中的三種回文鏈表的判斷方式，空間復雜度分別為O（N），O(N/2),O(1)

import java.util.*;/* public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;} }*/ public class Palindrome {public boolean isPalindrome(ListNode head) { if (head == null) {return false;}if (head.next == null) {return true;}ListNode fp = head;ListNode lp = head;while (fp.next != null && fp.next.next != null) {fp = fp.next.next;lp = lp.next;}ListNode n1 = lp.next;ListNode n2 = n1.next;ListNode n3 = null;lp.next = null;n1.next = null;while (n2 != null) { // 反向鏈接需要三個節點循環n3 = n2.next;n2.next = n1;n1 = n2;n2 = n3;}ListNode tail = n1;while (head != null && tail != null) {if (head.val == tail.val) {head = head.next;tail = tail.next;} else {n2 = n1.next;n1.next = null;while (n2 != null) {n3 = n2.next;n2.next = n1;n1 = n2;n2 = n3;}lp.next = n1;return false;}}n2 = n1.next;n1.next = null;while (n2 != null) {n3 = n2.next;n2.next = n1;n1 = n2;n2 = n3;}lp.next = n1;return true;} }

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的牛客网 在线编程 回文链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。