思路【我】：

1，計算鏈表長度

2，令A為較短鏈（如果B是短鏈，交換鏈表指針p和長度len）

3，長鏈B先遍歷gap個長度

4，開始遍歷，返回第一個相等點，遍歷結束還沒有相等點，就是沒有。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 思路：末端對齊，也就是長鏈先遍歷gap個長度// 然后遍歷，返回第一個相等點，遍歷結束還沒有相等點，就是沒有。ListNode pa = new ListNode();ListNode pb = new ListNode();// 1，計算鏈表長度int lenA = 0;int lenB = 0;pa = headA;pb = headB;while (pa != null) {pa = pa.next;lenA++;}while (pb != null) {pb = pb.next;lenB++;}// 2，令A為較短鏈（如果B是短鏈，交換鏈表指針p和長度len）pa = headA;pb = headB;if (lenA > lenB) {int temp = lenA;lenA = lenB;lenB = temp;ListNode tem = pa;pa = pb;pb = tem;}// 3，長鏈B先遍歷gap個長度int gap = lenB - lenA;while (gap-- > 0) {pb = pb.next;}// 4，開始遍歷while (pa != null) {if (pa == pb) {return pa;}pa = pa.next;pb = pb.next;}return null;}
}

思路【@靈艾山茶府】：

p和q終會相等，要么在交點，要么都是null。

• 假設A鏈條長度為x+z，B鏈表長度為y+z，其中z為相交后共同的長度。
  • 如果相交在交點，那么走過的路：p為x+z+y，q為y+z+x。
  • 如果相等在null，那么走過的路：p為x+y，q為y+x。（此時沒有z）

class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p = headA;ListNode q = headB;while (p != q) {p = p != null ? p.next : headB;q = q != null ? q.next : headA;}return p;}
}

思路【我】：

需要一個pre指針作為輔助，pre需要初始化為null不能為new ListNode()，因為這是反轉后的尾巴，如果是new ListNode的話會多了一個節點。

• 當指針p不為空的時候，遍歷。
  • 需要temp緩存p.next，即下一個要反轉的對象
  • 然后將p.next往前指向pre
  • pre指針到下一個對象，即p
  • p指針到下一個對象，即temp
• 最后當p為null的時候，證明pre是原鏈表的結尾，返回pre

class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode p = head;while (p != null) {ListNode temp = p.next;p.next = pre;pre = p;p = temp;}return pre;}
}

思路【我】：

反轉鏈表+中心擴散法。

1，算長度len

2，反轉左半部分

3，p是左半部分最后一位,temp=p.next，也就是右半部分的第一位了，所以right指向它。（如果len為奇數,temp是中間位置，中間位置的元素不用管,所以指針right = temp.next）

4，開始遍歷。p和right現在在中間，向兩遍擴散，一旦不相等返回false

5，遍歷后，全部相等，返回true

class Solution {public boolean isPalindrome(ListNode head) {// 思路：反轉鏈表+中心擴散法// 找到中間位置mid，分成兩半部分來處理// 左半部分，反轉鏈表// 左指針從中間往左遍歷，右指針從中間往右遍歷// 1，算長度lenint len = 0;ListNode p = head;while (p != null) {p = p.next;len++;}if (len == 1) {return true;}// 2，反轉前半部分ListNode pre = null;p = head;// 這個temp本來是可以在循環體內的臨時變量,但是下面需要用到,所以在外部定義.ListNode temp = p.next;for (int i = 0; i < len / 2; i++) {temp = p.next;p.next = pre;pre = p;// 這個if是為了,讓p留在左半部分的最后一位// p就是左半部分,反轉后,鏈表的頭if (i + 1 == len / 2) {break;}p = temp;}// 3，p是左半部分最后一位,temp=p.next，也就是右半部分的第一位了，所以right指向它ListNode right;if (len % 2 == 0) {right = temp;} else {// 如果len為奇數,temp是中間位置，中間位置的元素不用管,所以指針right指向下一個right = temp.next;}// 4，開始遍歷。p和right現在在中間，向兩遍擴散，一旦不相等返回falsewhile (p != null) {if (p.val != right.val) {return false;}p = p.next;right = right.next;}// 5，遍歷后，全部相等，返回truereturn true;}
}

加餐題目

傳統做法，先第一遍遍歷找到長度len，第二遍遍歷到n/2的位置，判斷奇偶數返回對應位置。和我上題的找中間節點的方法是一樣的。

但是這道題目，看了題解之后，看到@靈艾山茶府還可以用快慢指針法。

思路【@靈艾山茶府】：

快慢指針法，快指針走的速度是慢指針的2倍，當快指針到n，慢指針就是在中間位置。

class Solution {public ListNode middleNode(ListNode head) {// 快慢指針法，快指針走的速度是慢指針的2倍，當快指針到n，慢指針就是在中間位置ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
}

由此，234回文鏈表的做法，也可以直接調用反轉鏈表的方法，和尋找鏈表中間點的方法：

class Solution {public boolean isPalindrome(ListNode head) {ListNode mid = middleNode(head);ListNode right = reverseList(mid);ListNode left = head;// right：從 mid 到結束// left ：從開始到 midwhile (right != null) {if (left.val != right.val) {return false;}left = left.next;right = right.next;}return true;}// 876. 鏈表的中間結點private ListNode middleNode(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}// 206. 反轉鏈表private ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}return pre;}
}