【数据结构和算法】奇偶链表

发布时间:2024年01月16日

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集


文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1?方法一:分离节点后合并

三、代码

3.1?方法一:分离节点后合并

四、复杂度分析

4.1?方法一:分离节点后合并


前言

这是力扣的 328 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。

慢慢开始链表的模块了,这道题是一道非常好的队列的例题,很有代表性。


一、题目描述

给定单链表的头节点?head?,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。

第一个节点的索引被认为是?奇数?,?第二个节点的索引为?偶数?,以此类推。

请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在?O(1)?的额外空间复杂度和?O(n)?的时间复杂度下解决这个问题。

示例 1:

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

示例 2:

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

提示:

  • n ==??链表中的节点数
  • 0 <= n <= 104
  • -106?<= Node.val <= 106

二、题解

2.1?方法一:分离节点后合并

思路与算法:

如果链表为空,则直接返回链表。

对于原始链表,每个节点都是奇数节点或偶数节点。头节点是奇数节点,头节点的后一个节点是偶数节点,相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表,然后将偶数链表连接在奇数链表之后,合并后的链表即为结果链表。

原始链表的头节点 head 也是奇数链表的头节点以及结果链表的头节点,head 的后一个节点是偶数链表的头节点。令 evenHead = head.next,则 evenHead 是偶数链表的头节点。

维护两个指针 odd 和 even 分别指向奇数节点和偶数节点,初始时 odd = head,even = evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表,每一步首先更新奇数节点,然后更新偶数节点。

  • 更新奇数节点时,奇数节点的后一个节点需要指向偶数节点的后一个节点,因此令 odd.next = even.next,然后令 odd = odd.next,此时 odd 变成 even 的后一个节点。
  • 更新偶数节点时,偶数节点的后一个节点需要指向奇数节点的后一个节点,因此令 even.next = odd.next,然后令 even = even.next,此时 even 变成 odd 的后一个节点。

在上述操作之后,即完成了对一个奇数节点和一个偶数节点的分离。重复上述操作,直到全部节点分离完毕。全部节点分离完毕的条件是 even 为空节点或者 even.next 为空节点,此时 odd 指向最后一个奇数节点(即奇数链表的最后一个节点)。

最后令 odd.next = evenHead,将偶数链表连接在奇数链表之后,即完成了奇数链表和偶数链表的合并,结果链表的头节点仍然是 head。

如下图所示:


三、代码

3.1?方法一:分离节点后合并

Java版本:

class Solution {    
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode odd = head;
        ListNode evenHead = head.next;
        ListNode even = evenHead;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

C++版本:

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        ListNode* evenHead = head->next;
        ListNode* odd = head;
        ListNode* even = evenHead;
        while (even != nullptr && even->next != nullptr) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

Python版本:

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        
        evenHead = head.next
        odd, even = head, evenHead
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = evenHead
        return head

Go版本:

func oddEvenList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    evenHead := head.Next
    odd := head
    even := evenHead
    for even != nil && even.Next != nil {
        odd.Next = even.Next
        odd = odd.Next
        even.Next = odd.Next
        even = even.Next
    }
    odd.Next = evenHead
    return head
}

四、复杂度分析

4.1?方法一:分离节点后合并

  • 时间复杂度:O(n),其中 n?是链表的节点数。需要遍历链表中的每个节点,并更新指针。
  • 空间复杂度:O(1)。只需要维护有限的指针。

文章来源:https://blog.csdn.net/kologin/article/details/135616984
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。