英文链接:https://leetcode.com/problems/reorder-list/
中文链接:https://leetcode-cn.com/problems/reorder-list/
题目详述
给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
1
|
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
|
示例 2:
1
|
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
|
题目详解
可以分为三个步骤进行:
- 把链表从中间断开,分成前后两个链表。
- 翻转后面那个链表。
- 合并两个链表。
找到中间点可以使用快慢指针,也可以计算长度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
|
public class {
public void reorderList(ListNode head) { if (head == null || head.next == null) { return; } ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } ListNode s = slow.next; slow.next = null; ListNode h = reverse(s); while (h != null) { ListNode next = head.next; head.next = h; head = h; h = next; } }
private ListNode reverse(ListNode head) { ListNode cur = head; ListNode pre = null; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } }
|
近期评论