问题链接：LeetCode, GeeksforGeeks
思路
算法的核心在于找到链表的中点，将链表分成两部分，反转后半部分，然后交替合并两部分。
方法
-
找到链表的中点： 使用快慢指针法。慢指针每次移动一步，快指针每次移动两步。当快指针到达链表尾部时，慢指针指向链表的中点。
-
分割链表： 将链表从慢指针的下一个节点处断开，形成前半部分和后半部分两个链表。
-
反转后半部分： 使用迭代方法反转后半部分链表。
Lovefromio Github下载使用 `gh` CLI 与 GitHub 交互。通过`gh issue`、`gh pr`、`gh run` 和 `gh api` 管理 issue、PR、CI 运行以及高级查询。
-
合并链表： 交替合并前半部分和反转后的后半部分链表。
时间复杂度：O(n) 遍历链表一次。
空间复杂度：O(1) 只使用了常数个额外空间。
代码
<code class="java">/**
* 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;
}
}
}</code>
GitHub 仓库链接：[GitHub Repo Link](Replace with your actual GitHub repo link)
LeetCode 用户名：devn007
GeeksforGeeks 用户名：devnirwal16
