目录
题目：给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可
题目：给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
输入: head = [1,2,3,4] 输出: [1,4,2,3]
示例 2:
输入: head = [1,2,3,4,5] 输出: [1,5,2,4,3]
提示：
- 链表的长度范围为
[1, 5 * 104]1 <= node.val <= 1000
方法一:递归
/**
* 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) {
//出递归的条件
if(head == null || head.next == null || head.next.next == null){
return;
}
ListNode x = head;
//存储当前头结点的下一节点
ListNode p = x.next;
//存储当前头节点
ListNode y = head;
//找到尾节点de头节点
while(x.next.next != null){
x = x.next;
}
//找到尾节点，并存储
ListNode next = x.next;
//把尾节点的头节点置空
x.next = null;
//尾节点插入头结点的后面
//连接右边
next.next = p;
//连接左边
y.next = next;
//前面两个已经排列好，将第三个节点传入方法，调用递归
reorderList(y.next.next);
return;
}
}方法二：线性表
利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可
/**
* 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) {
//创建一个线性表用来存储
List<ListNode> list = new ArrayList<>();
while(head != null){
list.add(head);
head = head.next;
}
int i = 0;
int j = list.size() - 1;
head = list.get(0);
ListNode prev = head;
while(i < j){
prev.next = list.get(j);
i++;
prev.next.next = list.get(i);
j--;
prev = prev.next.next;
}
prev.next = null;
}
}方法三：快慢指针+链表反转+合并链表
注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。
这样我们的任务即可划分为三步：
1.找到原链表的中点（参考「876. 链表的中间结点」）。
我们可以使用快慢指针来 O(N)O(N)O(N) 地找到链表的中间节点。
2.将原链表的右半端反转（参考「206. 反转链表」）。
我们可以使用迭代法实现链表的反转。
3.将原链表的两端合并。
因为两链表长度相差不超过 111，因此直接合并即可。
/**
* 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) {
if(head == null || head.next == null || head.next.next == null){
return;
}
//快慢指针寻找中点+反转后半段链表+合并两个链表
ListNode midNode = mid(head);
//543
ListNode tail = reverse(midNode);
ListNode prev = head;
//12
//543
add(prev,tail);
}
public void add(ListNode l1 , ListNode l2){
while(l1 != null){
ListNode nextl1 = l1.next;
ListNode nextl2 = l2.next;
l1.next = l2;
l2.next = nextl1;
l1 = nextl1;
l2 = nextl2;
}
}
public static ListNode reverse(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
ListNode newHead = reverse(head.next);
next.next = head;
head.next = null;
return newHead;
}
public static ListNode mid(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;
}
}