Leetcode 876：给定一个头结点为 head 的非空单链表，返回链表的中间结点。

示例：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

思路：

此处用快慢双指针知识，快指针每次走两步，慢指针每次走一步。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!= null && fast.next != null){
            //有两个中间结点时，此处返回第二个。
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

当链表为偶数长度时候，可以任意返回中间结点的第一个或者第二个，上面代码返回的是第二个中间结点。想返回第一个中间结点只需要将while循环里面的判断条件改为

fast.next != null && fast.next.next != null即可。

    public ListNode findMid(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            //若写成fast != null && fast.next != null返回第二个中间结点
            //此处返回第一个中间结点
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

大家用测试用例[1,2,3,4,5,6]模拟一下即可。

Leetcode 234 : 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例：

输入：head = [1,2,2,1]
输出：true

解法1：利用线性表存储后判断

class Solution {
    public boolean isPalindrome(ListNode head) {
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode cur = head;
        while(cur != null){
            list.add(cur);
            cur = cur.next;
        }
        int i = 0, j = list.size() - 1;
        while(i < j){
            if(list.get(i).val == list.get(j).val){
                i++;
                j--;
            }
            else return false;
        }
        return true;
    }
} 

解法2：找到链表的中心结点，反转后半部分链表，然后在判断

class Solution {
    public boolean isPalindrome(ListNode head) {
        //先找到链表中间结点(第一个结点)。此结点后面的是后半部分链表，翻转后半部分链表，然后判断。
        ListNode mid = findmid(head);
        ListNode l2 = reverse(mid.next);
        while(l2 != null){
            if(l2.val == head.val){
                head = head.next;
                l2 = l2.next;
            }
            else return false;
        }
        return true;
        
    }

    public ListNode findmid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode temp;
        while(head != null){
            temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }

}

Leetcode143 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解法1：利用线性表进行重排,方便找到索引

class Solution {
    public void reorderList(ListNode head) {
        //前后双指针，最后结点的指针往前走，利用线性表。
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode cur = head;
        while(cur != null){
            list.add(cur);
            cur = cur.next;
        }
        int i = 0, j = list.size()-1;
        while(i < j){
            list.get(i).next = list.get(j);
            list.get(j).next = list.get(i+1);
            i++;
            j--;
        }
        list.get(i).next = null;
    }
}

解法2，将链表后半部分翻转，连接两个链表

class Solution {
    public void reorderList(ListNode head ) {
        //找到中间点，后半截链表翻转，拼接两个链表。
        ListNode mid = findMid(head);
        ListNode midd = mid.next;
        mid.next = null;
        
        ListNode l2 = reverse(midd);
        ListNode temp2;
        ListNode l1 = head;
        ListNode temp1;
        //head被改变了，找不到head
        while(l1 != null && l2 != null){
            temp1 = l1.next;
            temp2 = l2.next;
            l1.next = l2;
            l2.next = temp1;
            l1 = temp1;
            l2 = temp2;
        }
        

    }

    public ListNode findMid(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            //若写成fast != null && fast.next != null返回第二个中间结点
            //此处返回第一个中间结点
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;

    }
}