首页 > 试题广场 >

链表的奇偶重排

[编程题]链表的奇偶重排
  • 热度指数：101459 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。

数据范围：节点数量满足 ，节点中的值都满足
要求：空间复杂度 ，时间复杂度
示例1

输入

{1,2,3,4,5,6}

输出

{1,3,5,2,4,6}

说明

1->2->3->4->5->6->NULL
重排后为
1->3->5->2->4->6->NULL
示例2

输入

{1,4,6,3,7}

输出

{1,6,7,4,3}

说明

1->4->6->3->7->NULL
重排后为
1->6->7->4->3->NULL
奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3

备注:
链表长度不大于200000。每个数范围均在int内。

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
C
想去杭州的高级磨洋工在学习头像 想去杭州的高级磨洋工在学习
struct ListNode* oddEvenList(struct ListNode* head ) {
    if(head==NULL)
    {
        return NULL;
    }
    if(head->next==NULL||head->next->next==NULL)
    {
        return head;
    }
    struct ListNode* odd=head;
    struct ListNode* even=head->next;
    struct ListNode* node=head->next;
    while(even!=NULL&&even->next!=NULL)
    {
        struct ListNode* next = even->next;
        odd->next=even->next;
        even->next=next->next;
        odd=odd->next;
        even=even->next;
    }
    odd->next=node;
    return head;
}
编辑于 2024-04-13 23:01:32 回复(1)
C
可以找到心仪工作头像 可以找到心仪工作 
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    if (head == NULL || head->next == NULL){
        return head;
    }

    struct ListNode* pOdd = head;
    struct ListNode* pEven = head->next;
    struct ListNode* p = pEven;//保存偶数的第一个指针

    while(pOdd!=NULL && pEven!=NULL && pOdd->next!=NULL && pEven->next!=NULL)
    {
        pOdd->next = pEven->next;
        pOdd = pOdd->next;
        pEven->next = pOdd->next;
        pEven = pEven->next;
    } 
    pOdd->next = p;//连接奇偶
    return head;
}

发表于 2024-03-19 17:00:02 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
struct ListNode* oddEvenList(struct ListNode* head ) {
    struct ListNode *p;
    int *buffer[2],i,ListLen;
    if(head==NULL || head->next==NULL || head->next->next==NULL)
        return head;
    for(p=head,ListLen=0; p!=NULL; ListLen++,p=p->next) 
        ;
    buffer[0] = (int*)malloc((ListLen+1)/2*sizeof(int));
    buffer[1] = (int*)malloc(ListLen/2*sizeof(int));
    for(p=head,i=0; p!=NULL; i++,p=p->next) 
        buffer[i%2][i/2] = p->val;
    for(p=head,i=0; i<(ListLen+1)/2; i++,p=p->next) 
        p->val = buffer[0][i];
    for(i=0; i<ListLen/2; i++,p=p->next) 
        p->val = buffer[1][i];
    
    return head;
}

发表于 2024-03-15 23:26:47 回复(0)
C
在泡澡的喜羊羊很神奇头像 在泡澡的喜羊羊很神奇 
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    if(!head || !head->next || !head->next->next)
    {
        return head;
    }

    struct ListNode* s = head;
    struct ListNode* d = head->next;
    struct ListNode* dhead = d;

    while (s && d) {
        s->next=d->next;
        if(!s->next)
        {
            break;
        }
        s=s->next;
        d->next=s->next;
        d=d->next;
    }
    s->next = dhead;
    return head;

}

发表于 2023-05-27 12:29:28 回复(0)
C
三个和尚头像 三个和尚
不知道哪里错了，奇数个不行，偶数个可以，麻烦大佬看一下，感谢 
#include <stdio.h>
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    if (head == NULL || head->next == NULL || head->next->next == NULL) {
        return head;
    }
    struct ListNode* a = head; //奇数节点
    struct ListNode* b = head->next; //偶数节点
    struct ListNode* h2 = b; //第二个节点，备用，最后一个奇数节点指向此
    while (b->next->next != NULL && a->next->next != NULL) {
        a->next = a->next->next;
        b->next = b->next->next;
        a = a->next;
        b = b->next;
    }
    //总节点个数为奇数是要加一个，a再移动一次
    if (a->next->next!=NULL && b->next->next==NULL) {
        a->next = b->next;
        a = a->next;
        b->next = NULL;
    }else {
        a->next = NULL;
    }
    //将备用的h2付给a->next
    a->next = h2;
    return head;

}



发表于 2023-05-26 10:46:29 回复(1)
C
帅奶哟。头像 帅奶哟。 
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    int s[100000] = {0};
    int i = 0;
    int j;
    struct ListNode *p = head;
    //如果head为空，直接返回
    if (head == NULL) return head;

    //先将奇数号节点的val赋给s
    while (p) {
        s[i++] = p->val;
        p = p->next;
        if (p) {
            p = p->next;
        }
    }

    //将偶数号节点的val赋给s
    //p先指向第一个偶数节点
    p = head->next;
    while (p) {
        s[i++] = p->val;    //i在原有基础上赋值
        p = p->next;
        if (p) {
            p = p->next;
        }
    }

    //将s中的值一一重新赋给head
    p = head;
    i = 0;
    while (p) {
        p->val = s[i++];
        p = p->next;
    }

    return head;
}

发表于 2023-03-20 14:11:44 回复(0)
C
爱唱歌的黑眼圈头像 爱唱歌的黑眼圈
用两个数组分别存放奇偶号值；
再放回去 
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    int size1=0,size2=0;
    struct ListNode*p=head;
    int A[100005];
    int B[100005];
    int i=0;
    while(p){
        if(i%2==0){
            A[size1++]=p->val;
        }
        else{
            B[size2++]=p->val;
        }
        i++;
        p=p->next;
    }
    p=head;
    for(int i=0;i<size1;i++){
        p->val=A[i];
        p=p->next;
    }
    for(int i=0;i<size2;i++){
        p->val=B[i];
        p=p->next;
    }
    return head;
}


发表于 2023-02-23 11:49:56 回复(0)
C
Machinist.头像 Machinist. 
struct ListNode* oddEvenList(struct ListNode* head )
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    //odd：奇数；even：偶数；evenFirst：保存第一个偶数节点
    struct ListNode* odd = head, *even = head->next, *evenHead = head->next;

    while (odd->next != NULL && odd != NULL)
    {
        struct ListNode* oddPrev = odd, *evenPrev = even;   //记录odd和even当前值
        odd = odd->next->next;
        if (odd != NULL)
        {
            even = odd->next;
            evenPrev->next = even;
            oddPrev->next = odd;
            if (even == NULL)   //奇数用到（奇数输入{1, 2, 3}没问题，但其他的有问题）
            {
                odd->next = evenHead;
            }
        }
        else    //偶数用到
        {
            oddPrev->next = evenHead;
        }     
    }

    return head;
}
请大佬帮我分析一下，百思不得其解
您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起
您可以用printf在函数中打印信息分析问题
发表于 2022-10-27 21:16:25 回复(1)
C
冬xur头像 冬xur 
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    if(head==0||head->next==0)    return head;
    
    //至少存在两个结点
    struct ListNode* h1=head;
    struct ListNode* h2=head->next;struct ListNode* head2=h2;
    struct ListNode* pre_h1=0;
    struct ListNode* pre_h2=0;
    
    while(h1->next!=0&&h1->next->next!=0){
        pre_h1=h1;h1=h1->next->next;pre_h1->next=h1;
        if(h2->next->next!=0){
            pre_h2=h2;h2=h2->next->next;pre_h2->next=h2;
        }
    }
    h1->next=head2;h2->next=0;
    return head;
    
}

发表于 2022-08-21 19:52:21 回复(0)
C
和覅wEJVB头像 和覅wEJVB
struct ListNode* oddEvenList(struct ListNode* head ) 
{
    if(head==NULL || head->next==NULL)
    {
        return head;
    }
    struct ListNode *odd,*even,*evenhead;
    even=evenhead=head->next;
    odd=head;
    while(even!=NULL&&even->next!=NULL)
    {
        odd->next=odd->next->next;
        even->next=even->next->next;
        odd=odd->next;
        even=even->next;
    }
    odd->next=evenhead;
    return head;
}
发表于 2022-04-08 20:51:48 回复(0)
C
已注销头像 已注销 
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    struct ListNode *odd, *even, *prev_odd, *after_odd, *back;

    if (head == NULL || head->next == NULL || head->next->next == NULL) {
        return head;
    }
    prev_odd = NULL;
    after_odd = NULL;
    odd = head;
    back = even = head->next;
    while (even != NULL) {
        after_odd = even->next;
        even->next = (even->next != NULL ? even->next->next : NULL);
        odd->next = after_odd;
        prev_odd = odd;
        odd = after_odd;
        even = even->next;
    }
    if (odd != NULL) {
        odd->next = back;
    }
    else {
        prev_odd->next = back;
    }

    return head;
}

发表于 2022-03-23 19:55:53 回复(0)
C
李嘉图这样说道头像 李嘉图这样说道
请教一下为什么我这个会报错：输出超限:您的程序打印了太多的内容 
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    struct ListNode*p1,*p2;
    if(head==NULL) return head;
    p1=head; p2=head->next;
    while(p1->next && p1->next->next){
        p1->next=p1->next->next;
        p1=p1->next;
    }
    while(p2->next && p2->next->next){
        p2->next=p2->next->next;
        p2=p2->next;
    }
    p1->next=head->next;
    return head;
}
发表于 2022-03-22 21:55:02 回复(1)
C
莫小雨so头像 莫小雨so 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
#把偶数位置的节点提出来单独构成链表然后再将两个链表连起来
#include<stdlib.h>
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    if(head == NULL || head->next ==NULL) return head;
    struct ListNode *p , *q, *temp, *tail, *suc = NULL;
    tail = (struct ListNode *)malloc(sizeof(struct ListNode));
    suc = tail;
    int flag = 2;
    p = head;
    q = head->next;
    while(q!=NULL)
    {
        temp = q->next;
        if(flag % 2 == 0)
        {
            q->next =NULL;
            suc->next = q;
            q = temp;
            suc = suc->next;
        }
        else
        {
            p->next = q;
            q = temp;
            p = p->next;
        }
        flag ++;
    }
    p->next = tail->next;
    free(tail);
    return head;
}

发表于 2022-03-04 13:29:51 回复(0)
C
CreatorSY头像 CreatorSY

一

struct ListNode* oddEvenList(struct ListNode* head ) {
    struct ListNode *odd;
    struct ListNode *even = head;
    struct ListNode *tmp = head;
    struct ListNode *new;
    int len = 0;

    if (head == NULL)
        return NULL;

    new = head->next;
    odd = new;
    if (odd == NULL)
        return head;
    else
        tmp = odd->next;
    while(tmp != NULL) {
        if (len % 2 == 1) {
            odd->next = tmp;
            odd = odd->next;
        } else {
            even->next = tmp;
            even = even->next;
        }
        len++;
        tmp = tmp->next;
    }
    odd->next = NULL;
    even->next = new;
    return head;
}

二

struct ListNode* oddEvenList(struct ListNode* head ) {
    int *nums = NULL;
    int len = 0;
    struct ListNode* mid = head;
    struct ListNode* tai = head;

    if (head == NULL)
        return NULL;
    while(tai != NULL && tai->next != NULL) {
        len++;
        mid = mid->next;
        tai = tai->next->next;
    }
    if (tai != NULL)
        len = 2 * len + 1;
    else
        len = 2 * len;
    nums = calloc(sizeof(int), len);
    tai = head;
    for (int i = 0; i < len; i++, tai = tai->next)
        nums[i] = tai->val;
    tai = head;
    for (int i = 0; i < len; i++, tai = tai->next) {
        if (i < (len + 1) / 2)
            tai->val = nums[i * 2];
        else
            tai->val = nums[(i - (len + 1) / 2) * 2 + 1];
    }
    return head;
}
发表于 2022-01-07 23:44:23 回复(0)
C
牛客830308422号头像 牛客830308422号 
#define MAX_SIZE 200000
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    struct ListNode *p = head;
    int temp[MAX_SIZE] = {0};
    int idx = 0;

    while (p) {
        temp[idx++] = p->val;
        p = p->next;
    }
    p = head;
    for (int i = 0; i < idx; i += 2) {
        p->val = temp[i];
        p = p->next;
    }
    for (int i = 1; i < idx; i += 2) {
        p->val = temp[i];
        p = p->next;
    }
    return head;
}

发表于 2021-09-05 16:10:04 回复(0)
提交观点

问题信息

链表 排序
上传者：牛客332641号
难度：
16条回答 7214浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号