一、题目描述
给定一个单链表 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
二、题目解析
1、递归法
1-》2-》3-》4-》5，预期1-》5-》2-》4-》3
若一次把首尾交换
先得到1-》5，接下来把2-》3-》4交换，第二次交换完的结果是2-》4（剩余节点3还没处理）
第一次交换后的尾节点的next指针和第二次交换后的头指针连接：
1-》5-》2-》4，
第二次交换后尾节点的next指针和第三次交换后的头指针连接：
1-》5-》2-》4-》3
当剩余1个元素或者剩余2个元素的时候为递归出口（由于代码逻辑里会存在部分处理出现空指针异常，故需要特殊处理）
/**
* 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){
return;
}
change(head);
}
public ListNode change(ListNode head) {
//只有一个元素的特殊情况，不需要任何操作，直接返回头指针
if(head.next == null){
return head;
}
//nextStart、nextEnd为下轮递归调用的头指针，尾指针，为此轮调用的第二个元素，倒数第二个元素
ListNode start = head,nextStart = head.next,nextEnd = head,end = head;
//定位到尾节点
while(end.next != null){
end = end.next;
}
//定位到倒数第二个节点（是下轮递归的尾节点）
while(nextEnd.next != end){
nextEnd = nextEnd.next;
}
//只有两个元素的特殊情况，不需要任何操作，直接返回头指针
if(nextEnd == start){
return head;
}
head.next = end;
nextEnd.next = null;
end.next = change(nextStart);
return head;
}
}
2、利用反转链表（三指针法反转链表）
1-》2-》3-》4-》5，预期1-》5-》2-》4-》3
- 平均拆成2个链表：1-》2-》3,4-》5
- 第二个链表反转：1-》2-》3,5-》4
- 两个链表合并：1-》5-》2-》4-》3
代码如下：
/**
* 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){
return;
}
//平均拆成两个链表(考虑链表奇数个或者偶数个情况）
ListNode fast = head,slow = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode head1 = head,head2 = slow.next;
slow.next = null;
//反转链表2
head2 = reverse(head2);
//合并链表
ListNode tail = head1;
int count = 1;
head1 = head1.next;
while(head1 != null || head2 != null){
//这句不能放在head1和head2赋值之后，因为head1和head2值会改变
tail.next = count % 2 == 0 ? head1 : head2;
head1 = head1 ==null || count % 2 == 1 ? head1 : head1.next;
//注：不应用&&表示，因为不满足其中任一个，都不应该取next，否则会空指针异常
//head2 = head2 != null && count % 2 == 0 ? head2 : head2.next;
head2 = head2 == null || count % 2 == 0 ? head2 : head2.next;
tail = tail.next;
count++;
}
return;
}
public static ListNode reverse(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode prev = new ListNode();
prev.next = head;
ListNode cur = head,successor = head.next;
while(cur != null){
//testcase：1-》2-》3-》4
//注：prev指向会变，这种判断会导致断链（失去第1个，第2个节点）
//cur.next = prev.next == head ? null : prev;
//注：虚拟头结点不能用null来判断（改变prev指向，头结点内存仍存在），这样判断头指针和第一个节点会形成环
//cur.next = prev.next == null ? null : prev;
cur.next = cur == head ? null : prev;
prev = cur;
cur = successor;
//防止空指针异常
successor = successor == null ? null : successor.next;
}
return prev;
}
}
reverse方法优化：prev直接用null初始值，就不需要特殊判断头结点了
public static ListNode reverse(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode prev = null;
ListNode cur = head,successor = head.next;
while(cur != null){
//testcase：1-》2-》3-》4
//注：prev指向会变，这种判断会导致断链（失去第1个，第2个节点）
//cur.next = prev.next == head ? null : prev;
//注：虚拟头结点不能用null来判断（改变prev指向，头结点内存仍存在），这样判断头指针和第一个节点会形成环
//cur.next = prev.next == null ? null : prev;
cur.next = prev;
prev = cur;
cur = successor;
//防止空指针异常
successor = successor == null ? null : successor.next;
}
return prev;
}
合并链表优化：
//当第二个链表的头节点的指向空时，不进循环入
while(newHead != null){
//定义一个伪节点，存储第二个链表的第二节点
ListNode temp = newHead.next;
//将第二个链表的头节点，指向第一个链表链表的第二个节点。
newHead.next = head.next;
//将第一个链表的头节点，指向第二个链表的头节点。
head.next = newHead;
//将指向第一个链表的头节点的指针，移动到第一个链表的第二个节点
head = newHead.next;
//将指向第二个链表的头节点的指针，移动到第二个链表的第二个节点
newHead = temp;
}