【每日一题Day281】LC143 重排链表 | 快慢指针+反转链表

/**
 * 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 void reorderList(ListNode head) {
        // 找到中间节点
        ListNode end1 = findMiddlenode(head);
        // 反转后半部分节点
        ListNode start2 = reverseList(end1.next);
        end1.next = null;
        // 拼接链表
        ListNode p1 = head, p2 = start2;
        while (p2 != null){
            ListNode tmp1 = p1.next, tmp2 = p2.next;
            p1.next = p2;
            p2.next = tmp1;
            p1 = tmp1;
            p2 = tmp2;
        }
    }
    public ListNode reverseList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next; 
        }
        return pre;
    }
    public ListNode findMiddlenode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null){
            //  while (fast != null && fast.next != null){ 错误
            // 当链表中只有两个节点时，慢指针会移动一步
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

// 方法一 Java实现，使用数组存储节点
 class Solution {
    public void reorderList(ListNode head) {
        // 双指针的做法
        ListNode cur = head;
        // ArrayList底层是数组，可以使用下标随机访问
        List<ListNode> list = new ArrayList<>();  
        while (cur != null){
            list.add(cur);
            cur = cur.next;
        }
        cur = head;  // 重新回到头部
        int l = 1, r = list.size() - 1;  // 注意左边是从1开始
        int count = 0;
        while (l <= r){
            if (count % 2 == 0){
                // 偶数
                cur.next = list.get(r);
                r--;
            }else {
                // 奇数
                cur.next = list.get(l);
                l++;
            }
            // 每一次指针都需要移动
            cur = cur.next;
            count++;
        }
        // 注意结尾要结束一波
        cur.next = null;
    }
}

// 方法二：使用双端队列，简化了数组的操作，代码相对于前者更简洁（避免一些边界条件）
class Solution {
    public void reorderList(ListNode head) {
        // 使用双端队列的方法来解决
        Deque<ListNode> de = new LinkedList<>();
        // 这里是取head的下一个节点，head不需要再入队了，避免造成重复
        ListNode cur = head.next;  
        while (cur != null){
            de.offer(cur);
            cur = cur.next;
        }
        cur = head;  // 回到头部
        int count = 0;
        while (!de.isEmpty()){
            if (count % 2 == 0){
                // 偶数，取出队列右边尾部的值
                cur.next = de.pollLast();
            }else {
                // 奇数，取出队列左边头部的值
                cur.next = de.poll();
            }
            cur  = cur.next;
            count++;
        }
        cur.next = null;
    }
}