小学生都能看懂的题解 | #链表的奇偶重排#

问题描述

假设你有一串珠子，每个珠子上都有一个数字。我们要把这串珠子重新排列，使得奇数位置上的珠子都在前面，偶数位置上的珠子都在后面。

解决方法

我们可以用几个简单的步骤来完成这个任务：

1. 找出奇数位置的珠子：
1. 就像你玩游戏时，数着“1、2、3……”，奇数位置上的珠子就是“1、3、5……”位置上的珠子。
2. 找出偶数位置的珠子：
1. 偶数位置上的珠子就是“2、4、6……”位置上的珠子。
3. 重新连接珠子：
1. 把奇数位置的珠子连在一起，然后把偶数位置的珠子连在后面。

具体步骤

假设你有这样一串珠子：1, 2, 3, 4, 5, 6。

1. 找出奇数位置的珠子：
1. 奇数位置的珠子是：1, 3, 5。
2. 找出偶数位置的珠子：
1. 偶数位置的珠子是：2, 4, 6。
3. 重新连接珠子：
1. 把奇数位置的珠子连在一起：1 -> 3 -> 5。
2. 把偶数位置的珠子连在一起：2 -> 4 -> 6。
3. 最后，把奇数位置的珠子链表和偶数位置的珠子链表连在一起：1 -> 3 -> 5 -> 2 -> 4 -> 6。

示例

示例1

输入：{1, 2, 3, 4, 5, 6}

• 原链表：1 -> 2 -> 3 -> 4 -> 5 -> 6
• 重排后：1 -> 3 -> 5 -> 2 -> 4 -> 6

示例2

输入：{1, 4, 6, 3, 7}

• 原链表：1 -> 4 -> 6 -> 3 -> 7
• 重排后：1 -> 6 -> 7 -> 4 -> 3

代码实现

下面是一个简单的 Java 实现：

public class Solution {
    // 重排链表，奇数位节点在前，偶数位节点在后
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }

        // 创建两个虚拟头节点
        ListNode oddDummy = new ListNode(0);
        ListNode evenDummy = new ListNode(0);

        // 指向奇数位链表和偶数位链表的尾部
        ListNode oddTail = oddDummy;
        ListNode evenTail = evenDummy;

        // 用于遍历原链表
        ListNode current = head;
        int index = 1; // 用于区分奇数位和偶数位

        while (current != null) {
            if (index % 2 == 1) { // 奇数位
                oddTail.next = current;
                oddTail = oddTail.next;
            } else { // 偶数位
                evenTail.next = current;
                evenTail = evenTail.next;
            }
            current = current.next;
            index++;
        }

        // 将偶数位链表接到奇数位链表的后面
        oddTail.next = evenDummy.next;
        evenTail.next = null; // 防止形成环

        return oddDummy.next;
    }

如果这篇文章对你有帮助，请点个免费的赞👍，让它帮助更多的人。