Java教程

数据结构与算法-8.奇偶链表

本文主要是介绍数据结构与算法-8.奇偶链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

8、奇偶链表

题目

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 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

  • 应当保持奇数节点和偶数节点的相对顺序。
  • 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

8.0、直接解法

生成两个新链表,现在开始遍历原链表,遍历到奇数就把这个节点添加到奇链表后,遍历到偶数就把这个节点添加到偶链表后。

【1,2,3,4,5,6,7,8】

奇链表:【1,3,5,7】

偶链表:【2,4,6,8】

最后把两个链表拼接起来为

【1,3,5,7,2,4,6,8】

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

8.1、一般用法(最常用)

对于链表【1,2,3,4,5,6,7,8】

创建两个指针a,b初始指向1,2

  1. a . next = b . next a的下一个指向b的下一个也就是3
  2. a = a . next a指向3
  3. b . next = a . next b的下一个指向a的下一个也就是4
  4. b = b . next b指向4
  5. 以此类推

在最初需要记录2的索引,因为2是偶链表的开始,最后需要将奇链表的尾与偶链表的首拼接在一起。

ListNode* oddEvenList1(ListNode* head)
{
    if (!head || !head->next)return head;   //节点为空或者只有一个直接返回
    ListNode* tail = head->next;
    ListNode* oddNode = head;               //奇节点
    ListNode* evenNode = head->next;        //偶节点

    while (evenNode && evenNode->next)
    {
        oddNode->next = evenNode->next;
        oddNode = oddNode->next;
        evenNode->next = oddNode->next;
        evenNode = evenNode->next;
    }
    oddNode->next = tail;
    return head;
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
这篇关于数据结构与算法-8.奇偶链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!