每日一题——链表的奇偶重排

简介: 每日一题——链表的奇偶重排

链表的奇偶重排

题目链接

思路一

  • 首先需要明确,题目所说的奇偶是节点编号的奇偶,而不是节点数据的奇偶。
  • 既然如此,我们就可以把链表编号为奇数的节点一起放入一个新建链表,将编号为偶数的节点一起放入另一个新建链表,最后再将连个链表合并即可。

具体步骤

  • 首先定义两个链表头odd,even分别存放编号为奇数、偶素的节点。
  • 再定义三个指针变量cur1,cur2,cur3使其分别指向原链表的头,odd的头,even的头,定义count并初始化为1,代表节点编号
  • 对原链表进行遍历,当count为奇数,则将cur1所代表的节点放入odd,否则放入even。每放入一个节点,都令count加1,cur1下滑一个节点,直到cur1为空,即走到表尾。
  • 最后,将even接到odd后面,再返回odd即可。

实现代码

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* oddEvenList(struct ListNode* head ) {
    struct ListNode *odd = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *even = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *cur1 = head, *cur2 = odd, *cur3 = even;
    int count = 1;
    while(cur1)
    {
        if(count % 2)
        {
            cur2->next = cur1;
            cur2 = cur1;
        }
        else 
        {
            cur3->next = cur1;
            cur3 = cur1;
        }
        cur1 = cur1->next;
        count++;
    }
    cur2->next = even->next;    //odd和even的头结点都没有存入具体的数据,因此需要舍去
    cur3->next = NULL;      //令表尾为空
    return odd->next;   //返回第一个有效节点
}

思路二

  • 我们可以简单得到,链表第一个节点为奇,第二个为偶,第三个为奇,第四个为偶········
  • 那么,我们就可以定义两个指针变量odd,even使其分别指向第一个奇节点,第一个偶节点
  • 断开odd与even的连接,使odd指向even的下一个节点(即下一个奇节点),令odd为下一个奇节点,接着,令even指向odd的下一个节点(即下一个偶节点),并令even为下一个偶节点。
  • 重复第三步,直到even或even的下一个节点为空,这样我们就将所有的奇节点连接到一起,所有的偶节点连接到一起了。
  • 但是,怎么将他们链接成一个链表呢?我们好像找不到所有偶节点的头,因此,我们可以在最开始定义一个指针evenhead来代表偶节点的头,并使其为第一个偶节点,这样不就可以成功链接了吗。
  • 如图:

具体步骤

  • 首先对链表进行判断,当链表为空,只有一个或两个节点时,不需要进行奇偶重排,直接返回头结点
  • 定义两个指针变量odd,even,使其分别指向第一个奇节点,第一个偶节点
  • 定义evenhead,保存第一个偶节点
  • 断开odd与even的连接,使odd指向even的下一个节点(即下一个奇节点),令odd为下一个奇节点,接着,令even指向odd的下一个节点(即下一个偶节点),并令even为下一个偶节点,直到even或even的下一个节点为空。
  • 令odd指向evenhead完成链接
  • 返回head

实现代码

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* oddEvenList(struct ListNode* head ) {
    if(head == NULL || head->next == NULL || head->next->next == NULL)
        return head;
    struct ListNode *odd = head ,*even = head->next, *evenhead = head->next;
    while(even && even->next)
    {
          //odd连接even的后一个,即奇数位
            odd->next = even->next;
            //odd进入后一个奇数位
            odd = odd->next;
            //even连接后一个奇数的后一位,即偶数位
            even->next = odd->next;
            //even进入后一个偶数位
            even = even->next;
     }
    //even整体接在odd后面
    odd->next = evenhead; 
    return head;
}


相关文章
|
4月前
|
索引 Python
【Leetcode刷题Python】328. 奇偶链表
在不使用额外空间的情况下,将链表中的奇数和偶数索引节点重新排序的方法,并提供了相应的Python实现代码。
36 0
|
7月前
|
索引
每日一题:力扣328. 奇偶链表
每日一题:力扣328. 奇偶链表
44 4
|
7月前
|
Rust 索引
Rust 编程小技巧摘选(6)
Rust 编程小技巧摘选(6)
84 1
Rust 编程小技巧摘选(6)
|
7月前
|
Java Go C++
Golang每日一练(leetDay0118) 扁平化嵌套列表迭代器、整数拆分
Golang每日一练(leetDay0118) 扁平化嵌套列表迭代器、整数拆分
59 0
Golang每日一练(leetDay0118) 扁平化嵌套列表迭代器、整数拆分
|
7月前
|
Java Go C++
Golang每日一练(leetDay0113) 奇偶链表、链表随机节点
Golang每日一练(leetDay0113) 奇偶链表、链表随机节点
61 0
Golang每日一练(leetDay0113) 奇偶链表、链表随机节点
|
7月前
|
算法 程序员
【算法训练-链表 七】【链表排序】:链表排序、链表的奇偶重排、重排链表
【算法训练-链表 七】【链表排序】:链表排序、链表的奇偶重排、重排链表
68 1
|
7月前
|
存储 Java 容器
leetcode-143:重排链表
leetcode-143:重排链表
38 0
|
7月前
|
Go
golang力扣leetcode 143.重排链表
golang力扣leetcode 143.重排链表
45 0
|
7月前
|
算法
leetcode-328:奇偶链表
leetcode-328:奇偶链表
48 0
|
7月前
【每日一题Day281】LC143 重排链表 | 快慢指针+反转链表
【每日一题Day281】LC143 重排链表 | 快慢指针+反转链表
50 0