> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-12-2022-234.md).

# 01/12/2022 234

Palindrome Linked List

method 1:

using stack to store each node value. And then compare the value with the node value in the linkedlist.

Time O(n)

Space O(n)

![](https://423021406-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mjjyb1BqScHCWaFFmF4%2Fuploads%2FGhfzzA824kZxROj5gL1v%2Fimage.png?alt=media\&token=c891e1f0-5def-43a1-b50e-6bbd821f1118)

method 2:

find the end of the first half the list.  Reverse the second half the list. check if it is palindrome. Then restore the list and return the result.

Time O(n)

Space O(1)

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

```
ListNode fistHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(fistHalfEnd.next);

ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while(result && p2 != null){
    if(p1.val != p2.val) result = false;
    p1= p1.next;
    p2 = p2.next;
}

fistHalfEnd.next = reverseList(secondHalfStart);
return result;
```

} private ListNode reverseList(ListNode head){ if(head == null || head.next == null) return head;

```
  ListNode prev = null;
  while(head != null){
      ListNode nextTemp = head.next;
      head.next = prev;
      prev = head;
      head = nextTemp;
  }
  return prev;
```

}

private ListNode endOfFirstHalf(ListNode head){ ListNode slow = head; ListNode fast = head;

```
 while(fast.next != null && fast.next.next != null){
     fast = fast.next.next;
     slow = slow.next;
 }
 return slow;
```

}