重新订购列表：LC培养基，GFG硬

问题链接：LeetCode, GeeksforGeeks

思路

算法的核心在于找到链表的中点，将链表分成两部分，反转后半部分，然后交替合并两部分。

方法

1. 找到链表的中点： 使用快慢指针法。慢指针每次移动一步，快指针每次移动两步。当快指针到达链表尾部时，慢指针指向链表的中点。

2. 分割链表： 将链表从慢指针的下一个节点处断开，形成前半部分和后半部分两个链表。

3. 反转后半部分： 使用迭代方法反转后半部分链表。

4. 合并链表： 交替合并前半部分和反转后的后半部分链表。

   

   扣子编程

   扣子推出的AI编程开发工具

   下载

时间复杂度：O(n) 遍历链表一次。

空间复杂度：O(1) 只使用了常数个额外空间。

代码

/**
 * 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 reverse(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = head.next;
        while(curr != null){
            curr.next = prev;
            prev = curr;
            curr = next;
            if (next != null) {
                next = next.next;
            }
        }
        return prev;
    }
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) return;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode second = slow.next;
        slow.next = null;
        second = reverse(second);
        ListNode first = head;
        while(second != null){
            ListNode temp = first.next;
            first.next = second;
            second = second.next;
            first.next.next = temp;
            first = temp;
        }
    }
}

GitHub 仓库链接：[GitHub Repo Link](Replace with your actual GitHub repo link)

LeetCode 用户名：devn007

GeeksforGeeks 用户名：devnirwal16