算法训练营第一期 | 奇偶链表

一、题目描述

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

  • 应当保持奇数节点和偶数节点的相对顺序。
  • 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

二、题目解析

三、参考代码

class Solution {
    public ListNode oddEvenList(ListNode head) {

        // 边界情况处理,如果链表为空或者只有一个节点,返回 head 就行
        if(head == null || head.next == null ) return head;

        // 设置一个指针,指向链表的头节点,odd 代表奇数节点的头节点
        ListNode odd = head;

        // 设置一个指针,指向链表的头节点的下一个节点,even 代表偶数节点的头节点
        ListNode even = head.next; 

        // 设置一个指针,指向偶数节点的头节点,最终让奇数节点的尾节点的 next 指针指向它
        ListNode evenHead = even;

        // 从偶数链表的头节点开始向后遍历
        // 如果当前节点为空,或者后一节点为空,那么说明整个链表已经查看完毕,不需要再遍历了
        while(even != null && even.next != null){
            // 原先奇数节点的下一个节点是偶数节点,即 even 这个节点
            // 根据数学知识,奇数后面一定是偶数,偶数后面一定是奇数
            // 那么 even.next 节点必然是奇数节点
            // 所以让 odd 这个奇数节点的 next 指针指向 even.next 这个奇数节点
            // 这样,odd 上面都是奇数
            odd.next = even.next;
            // 让 odd 移动到最新的由奇数节点组成的链表的尾部位置
            odd = odd.next;

            // 这个时候,odd.next 必然是偶数节点
            // 所以让 even 这个偶数节点的 next 指针指向 odd.next 这个偶数节点
            even.next = odd.next;
            // 让 even 移动到最新的由偶数节点组成的链表的尾部位置
            even = even.next;
        }

        // 此时,原链表所有的节点已经遍历完毕
        // odd 上都是奇数节点
        // even 都是偶数节点
        // 根据题目要求,奇数节点都在偶数节点之前
        // 所以让此时右奇数节点组成的链表的尾部的 next 指针指向由偶数节点组成的链表的头部
        odd.next = evenHead;

        // 最后返回原链表的头部节点就可以了
        // 链表的头部节点没有发生过变化,因为它是奇数节点,并且是第一个奇数节点
        return head;

    }
}

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注