重排链表 | 徐年の博客

力扣 143. 重排链表

题目说明

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

提示：

链表的长度范围为 [1, 5 * 10^4]
1 <= node.val <= 1000

示例

示例 1:

1 2	输入: head = [1,2,3,4] 输出: [1,4,2,3]

示例 2:

1 2	输入: head = [1,2,3,4,5] 输出: [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 another = slow.next;
        slow.next = null;

        // 翻转后半截链表
        ListNode pre = null;
        ListNode now = another;
        ListNode last = now;

        while (now != null) {
            last = now.next;
            now.next = pre;
            pre = now;
            now = last;
        }

        // 保存翻转的链表
        another = pre;

        // 两链表合并
        ListNode cur = head;
        while (cur != null && another != null) {
            // 要链接的下一个节点
            ListNode curNext = another;
            another = another.next;
            // 主链表的下一个节点
            ListNode nextNode = cur.next;
            curNext.next = cur.next;
            cur.next = curNext;

            cur = nextNode;
        }

    }


}