一、题目描述
给定一个单链表 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、使用线性表
我们知道，线性表是可以按照下标直接取数据的。我们可以把链表的节点依次存入线性表中，再重新拼接即可。
/** * 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<>(); ListNode p = head; while(p!=null){ //将链表放入list中 list.add(p); p = p.next; } int i = 0; int j = list.size()-1; ListNode q = new ListNode(0); while(i<j){ list.get(i).next = list.get(j); i++; if(i == j){ //链表长度为奇数或偶数的情况要分开处理 break; } list.get(j).next = list.get(i); j--; } //防止成环 list.get(i).next = null; } }
时间复杂度： O(N)
空间复杂度： O(N)
二、直接在原链表上修改
找到链表中点，将后半部分翻转，再拼接回原链表
class Solution { public void reorderList(ListNode head) { if (head == null) { return; } ListNode mid = middleNode(head); ListNode l1 = head; ListNode l2 = mid.next; //把前半部分和后半部分链表断开 mid.next = null; l2 = reverseList(l2); mergeList(l1, l2); } public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } public void mergeList(ListNode l1, ListNode l2) { ListNode l1_tmp; ListNode l2_tmp; while (l1 != null && l2 != null) { l1_tmp = l1.next; l2_tmp = l2.next; l1.next = l2; l1 = l1_tmp; l2.next = l1; l2 = l2_tmp; } } }
时间复杂度： O(N)
空间复杂度： O(1)
