题解 | #重排链表#

1
//通过快慢指针把链表分为前后两部分，先反转后半部分，将反转后的后半部分插入前半部分，即可得到新的链表
import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
 
        ListNode pre = new ListNode(-1);
        pre.next = head;

//通过快慢指针把链表分为前后两部分。
        ListNode fast = pre;
        ListNode slow = pre;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
 
        }

//反转后半部分
        ListNode right = slow.next;
        slow.next = null;
        if (right != null && right.next != null) {
            ListNode before = right;
            ListNode next = right.next;
            before.next = null;
            while (next != null) {
                ListNode oddNext = next.next;
                next.next = before;
                before = next;
                next = oddNext;
            }
            right = before;
        }

//将反转后的后半部分插入前半部分，即可得到新的链表
        fast = head;
        while (right != null) {
            ListNode oddNext = fast.next;
            ListNode  newRight = right.next;
            fast.next = right;
            right.next = oddNext;
            fast = oddNext;
            right = newRight;
 
        }
 
 
    }
}