Question link: https://leetcode-cn.com/problems/palindrome-linked-list/submissions/
Question-solving ideas:
Cut in half, reverse the second half, and compare whether the two halves are equal.
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode(int x) {val = x;}
7 *}
8 */
9 class Solution {
10 public boolean isPalindrome(ListNode head) {
11 if(head==null||head.next==null)
12 return true;
13 ListNode fast = head;
14 ListNode slow = head;
15 while(fast!=null && fast.next!=null)
16 {
17 slow= slow.next;
18 fast = fast.next.next;
19 }
20 if(fast!=null)
21 slow = slow.next;
22 cut(head,slow);
23 return isEqual(head,reverse(slow));
24
25 }
26 public void cut(ListNode head,ListNode cutnode)
27 {
28 while(head.next!=cutnode)
29 {
30 head= head.next;
31 }
32 head.next = null;
33 }
34 public ListNode reverse(ListNode head)
35 {
36 ListNode pre = null;
37 ListNode sec = null;
38 while(head!=null)
39 {
40 sec = head.next;
41 head.next = pre;
42 pre = head;
43 head = sec;
44 }
45 return pre;
46 }
47
48 private boolean isEqual(ListNode l1, ListNode l2) {
49 while (l1 != null && l2 != null) {
50 if (l1.val != l2. val) return false;
51 l1 = l1.next;
52 l2 = l2.next;
53 }
54 return true;
55 }
56 }
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode(int x) {val = x;}
7 *}
8 */
9 class Solution {
10 public boolean isPalindrome(ListNode head) {
11 if(head==null||head.next==null)
12 return true;
13 ListNode fast = head;
14 ListNode slow = head;
15 while(fast!=null && fast.next!=null)
16 {
17 slow= slow.next;
18 fast = fast.next.next;
19 }
20 if(fast!=null)
21 slow = slow.next;
22 cut(head,slow);
23 return isEqual(head,reverse(slow));
24
25 }
26 public void cut(ListNode head,ListNode cutnode)
27 {
28 while(head.next!=cutnode)
29 {
30 head= head.next;
31 }
32 head.next = null;
33 }
34 public ListNode reverse(ListNode head)
35 {
36 ListNode pre = null;
37 ListNode sec = null;
38 while(head!=null)
39 {
40 sec = head.next;
41 head.next = pre;
42 pre = head;
43 head = sec;
44 }
45 return pre;
46 }
47
48 private boolean isEqual(ListNode l1, ListNode l2) {
49 while (l1 != null && l2 != null) {
50 if (l1.val != l2. val) return false;
51 l1 = l1.next;
52 l2 = l2.next;
53 }
54 return true;
55 }
56 }