143. 重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
1.入栈法
思路：(使用栈进行反转)
- 使用快慢指针找到链表中点
- 将链表中点之后的元素压入栈
- 依次将元素出栈（目的是反转）然后进行拼接即可
- 注意：找到链表中点之后，一定要将后面置空
public static class ListNode {
private int val;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
//用于测试用例
public ListNode(int[] arr) {
if (arr == null || arr.length == 0) throw new NullPointerException("array is Empty");
this.val = arr[0];
ListNode cur = this;
for (int i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
ListNode cur = this;
while (cur != null) {
res.append(cur.val + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
private static void reordList2(ListNode head) {
if (head == null) return;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
Stack<ListNode> stack = new Stack<>();
ListNode next = slow.next;
while (next != null) {
stack.push(next);
next = next.next;
}
slow.next = null;
ListNode cur = head;
while (!stack.isEmpty()) {
ListNode node = new ListNode(stack.pop().val);
node.next = cur.next;
cur.next = node;
cur = cur.next.next;
}
}
复杂度分析：
时间复杂度：O(n + n / 2 + n / 2), 时间复杂度是遍历链表 + 遍历右半部分链表 + 遍历栈
空间复杂度：O(n / 2 + n / 2), 空间复杂度为 栈所占用的空间 + 新建的链表所占用的空间
-
2. 反转+指针
思路：优化方法1
- 先使用快慢指针找到整个链表的中点
- 将中点后面的后半部分链表进行反转
-
将反转后的链表拼接到原链表即可
image.png
private static void reordList(ListNode head) {
if (head == null) return;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
//将后半部分链表反转
ListNode rev = reverse2(slow.next);
//将链表断开
slow.next = null;
ListNode cur = head;
while (rev != null) {
ListNode p = rev.next;
rev.next = cur.next;
cur.next = rev;
rev = p;
cur = cur.next.next;
}
}
/**
* 反转链表
* @param head
* @return
*/
private static ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
/**
* 递归反转
* @param head
* @return
*/
private static ListNode reverse2(ListNode head) {
if (head == null || head.next == null) return head;
ListNode cur = reverse2(head.next);
head.next.next = head;
head.next = null;
return cur;
}
复杂度分析：
时间复杂度：O(n + n/2): n为链表长度, 复杂度为两次遍历的时间
空间复杂度：O(1)
-
测试用例
public static void main(String[] args) {
int[] arr = new int[] {1, 2, 3, 4, 5};
ListNode listNode = new ListNode(arr);
System.out.println(listNode);
System.out.println("重排链表" + reordList(listNode));
}
-
结果
1->2->3->4->5->NULL
重排链表1->5->2->4->3->NULL
-
源码
-
我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正
- Github
