首页 > 试题广场 >

链表的奇偶重排

[编程题]链表的奇偶重排
  • 热度指数:98971 时间限制: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,点此查看相关信息
画图过一遍就懂,简单明了。
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if(head == null || head.next == null) return head;
        ListNode evenHead = head.next;
        ListNode odd = head,even = head.next;
        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;
    }


发表于 2020-09-23 16:28:44 回复(7)
如果有奇数个链表,记得把偶数节点链表的最后一个节点的next属性设置为null,否则会出现环形链表然后报错,debug了好久踩了这个坑
发表于 2022-09-02 15:42:25 回复(1)
    public ListNode oddEvenList(ListNode head) {
       if(head==null) return  head;
       //无需对头节点做操作 不用dummyHead
        //奇链表头位于head 偶链表头位于head.next
        ListNode oddHead = head,evenHead = head.next;
        ListNode odd = oddHead,even = evenHead;
        //终止条件:因为even走在前面 一定先终止 所以判断条件就是它
        //节点总数为偶数个时 even.next为null
        //节点总数为奇数个时: even==null  这俩条件触发一个就跳出循环
        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;
    }

发表于 2021-03-15 19:11:26 回复(1)
class Solution:
    def oddEvenList(self , head: ListNode) -> ListNode:
        # write code here
        evenHead = head.next # 偶数的第一个
        odd = head # 奇数
        even = head.next # 偶数
        while even and even.next:
            odd.next = even.next # 奇数指向奇数
            odd = odd.next
            even.next = odd.next # 偶数指向偶数
            even = even.next
        odd.next = evenHead # 奇数最后一个指向偶数第一个
        return head
发表于 2022-04-25 23:04:51 回复(2)
开始没看题目以为按值来奇偶重组,把问题想复杂了……
按值:
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        ListNode* odd = head, *even = head, *curr, *pre;
        if (head->val % 2 == 0) {
            while (odd && odd->val % 2 == 0) {
                odd = odd->next;
            }
            pre = odd;
            curr = odd->next;
        } else {
            while (even && even->val % 2 == 1) {
                even = even->next;
            }
            pre = even;
            curr = even->next;
        }
        while (curr) {
            if (curr->val % 2 == 1) {
                if (pre == even) {
                    pre->next = curr->next;
                    curr->next = odd->next;
                    odd->next = curr;
                    curr = pre->next;
                    odd = odd->next;
                }else {
                    odd = odd->next;
                    pre = pre->next;
                    curr = curr->next;
                }
            } else {
                if (pre == odd) {
                    pre->next = curr->next;
                    curr->next = even->next;
                    even->next = curr;
                    curr = pre->next;
                    even = even->next;
                }else {
                    even = even->next;
                    pre = pre->next;
                    curr = curr->next;
                }
            }
        }
        return head;
    }
};
按编号:
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        if(head==nullptr) return nullptr;
        ListNode *evenhead=head->next, *odd=head, *even=evenhead;
        while (even&&even->next) {
            odd->next = even->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }
        odd->next = evenhead;
        return head;
    }
};



发表于 2023-09-02 14:08:17 回复(0)
双指针
function oddEvenList( head ) {
    // write code here
    if(!head) return head
    let odd = head       ///扫描奇链节点
    let even = head.next  ///扫描偶链节点
    let evenHead = even    //保存偶数链的节点
    while(even&&even.next){
        odd.next = odd.next.next //指向下一个奇数节点
        even.next = even.next.next //指向下一个奇数节点
        odd = odd.next  //odd推进到下一个奇数节点
        even = even.next //even推进到下一个偶数节点
    }
    odd.next = evenHead //奇数链连上偶数链
    return head
}

发表于 2020-12-17 16:32:43 回复(2)
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        //假设第一个节点为奇数,所以在代码中体现出来最后一个奇数节点必定指向第一个偶数节点,
        //原地算法:使空间复杂度为常数。定义odd,even,evenHead.每次都向前推进,只不过奇数找奇数,偶数找偶数。
        if(head == null) return null;
        ListNode odd = head,even = odd.next,evenHead = even;
        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;
    }
}

发表于 2020-11-04 11:08:24 回复(0)
第二种方法来了, 放到两个数组里面,再加会链表里去
public ListNode oddEvenList (ListNode head) {
        // write code here
        ListNode cur = head;
        ArrayList<Integer> even = new ArrayList<Integer>();
        ArrayList<Integer> odd = new ArrayList<Integer>();
      
        int i = 0;
        while (cur != null) {
            if (i % 2 == 0) {
                even.add(cur.val);
            } else {
                odd.add(cur.val);
            }
            cur = cur.next;
            ++i;
        }
        
        cur = head;
        for (int j = 0; j < even.size();j++) {
           cur.val = even.get(j);
            cur = cur.next;
        }
        for (int K = 0; K < odd.size();K++) {
           cur.val = odd.get(K);
              cur = cur.next;
        }
        return head;
        
    }
发表于 2022-04-26 14:34:34 回复(0)
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if (head==null)return head;
        ListNode ji=head;
        ListNode ou=head.next;
        ListNode jiCur=ji;
        ListNode ouCur=ou;
        //分别建立奇链表和偶链表,然后将两个链表连起来
        while (jiCur!=null&&ouCur!=null&&jiCur.next!=null&&ouCur.next!=null){
            jiCur.next=jiCur.next.next;
            jiCur=jiCur.next;
            ouCur.next=ouCur.next.next;
            ouCur=ouCur.next;
        }
        jiCur.next=ou;
        return ji;
    }

发表于 2021-07-15 17:15:06 回复(0)
果然还是别人题解更强
原来的思路按照奇偶节点拆分为两个链表,然后在进行合并,代码显得很长。。。,而且要新开节点
/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 *    ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here
//         if(head == NULL) return head;
//         ListNode *oldhead = head, *evenhead = head->next;
//         ListNode *oldp = head, *evenp = evenhead;
//         while(evenp != NULL && evenp->next != NULL){
//             oldp->next = evenp->next;
//             oldp = oldp->next;
//             evenp->next = oldp->next;
//             evenp = evenp->next;
//         }
//         oldp->next = evenhead;
//         return head;
        if(head == NULL) return head;
        ListNode *ohead = new ListNode(0), *ehead = new ListNode(0);
        ListNode *p = head, *p1 = ohead, *p2 = ehead;
        int cnt = 1;
        while(p != NULL){
            ListNode *tmp = p->next;
            if(cnt%2 == 1){
                p->next = p1->next;
                p1->next = p;
                p1 = p1->next;
            }
            else{
                p->next = p2->next;
                p2->next = p;
                p2 = p2->next;
            }
            p = tmp;
            ++cnt;
        }
        p1->next = ehead->next;
        ehead->next = NULL;
        free(ehead);
        ohead->next = NULL;
        free(ohead);
        return head;
    }
};









参考别人解法,代码简洁简洁了很多,不用新开头结点,大概思路就是在原链表直接进行操作,按照奇偶节点拆分为两个链表,然后进行合并
/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 *    ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        if(head == NULL) return head;
        ListNode *oldhead = head, *evenhead = head->next;
        ListNode *oldp = head, *evenp = evenhead;
        while(evenp != NULL && evenp->next != NULL){
            oldp->next = evenp->next;
            oldp = oldp->next;
            evenp->next = oldp->next;
            evenp = evenp->next;
        }
        oldp->next = evenhead;
        return head;
//         if(head == NULL) return head;
//         ListNode *ohead = new ListNode(0), *ehead = new ListNode(0);
//         ListNode *p = head, *p1 = ohead, *p2 = ehead;
//         int cnt = 1;
//         while(p != NULL){
//             ListNode *tmp = p->next;
//             if(cnt%2 == 1){
//                 p->next = p1->next;
//                 p1->next = p;
//                 p1 = p1->next;
//             }
//             else{
//                 p->next = p2->next;
//                 p2->next = p;
//                 p2 = p2->next;
//             }
//             p = tmp;
//             ++cnt;
//         }
//         p1->next = ehead->next;
//         ehead->next = NULL;
//         free(ehead);
//         ohead->next = NULL;
//         free(ohead);
//         return head;
    }
};












编辑于 2021-05-26 14:39:07 回复(0)
解题思路:使用标记每两次,跳过一个节点,并将其单独加到偶数节点后面,最后把偶数链放到奇数链后面
import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        int flag=0;
        ListNode odd=new ListNode(0);
        ListNode node=odd;
        ListNode pre=head;
        ListNode cur=head;
        while(cur!=null){
            if(flag%2==1){
                pre.next=cur.next;
                ListNode temp=cur;
                temp.next=null;
                odd.next=temp;
                odd=odd.next;
                cur=pre;
            }
            pre=cur;
            cur=cur.next;
            flag++;
        }
        pre.next=node.next;
        return head;
    }
}


发表于 2021-03-16 14:09:17 回复(0)
将链表拆分为两个链表: 奇数位链表、偶数位链表,然后拼接到一起返回。
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // 空链表或者只有一个结点
        if(!head || !head->next) {
            return head;
        }
        
        ListNode *oddHead = new ListNode(0), *everHead = new ListNode(0);
        ListNode *odd = oddHead, *ever = everHead;
        
        int id = 0;
        ListNode *p = head;
        while(p) {
            if((++id) % 2 == 0) {
                odd->next = p;
                odd = p;
            }
            else {
                ever->next = p;
                ever = p;
            }
            p = p->next;
        }
        ever->next = NULL;
        odd->next = NULL;
        
        ever->next = oddHead->next;
        return everHead->next;
    }
};


发表于 2020-10-02 15:59:00 回复(0)
struct ListNode* oddEvenList(struct ListNode* head ) {
   if(head==NULL || head->next==NULL)return head;
   struct ListNode* odd=head,*even=head->next;
   struct ListNode* p=head->next->next,*q=even;
   int cnt=0;
   while(p)
   {
        cnt++;
        if(cnt%2==1)
        {
            odd->next=p;
            odd=p;
        }
        else {
            even->next=p;
            even=p;
        }
        p=p->next;
   }
   even->next=NULL;
   odd->next=q;
   return head;
}
时间复杂on,空间复杂度o1
发表于 2023-10-02 18:29:18 回复(0)
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def oddEvenList(self , head: ListNode) -> ListNode:
        # write code here
        if not head: return None 
        oddHead = head.next 
        # 奇偶指针
        left, right = head, head.next 
        while right and right.next:
            left.next = right.next 
            left = left.next 
            right.next = left.next 
            right = right.next 
        left.next = oddHead
        return head


发表于 2023-09-05 10:13:10 回复(0)
class Solution:
    def oddEvenList(self , head: ListNode) -> ListNode:
        # write code here
        odd_head = ListNode(0)
        even_head = ListNode(0)
        p_odd = odd_head
        p_even = even_head
        flag = True
        p = head
        while p:
            if flag:
                p_odd.next = p
                p_odd = p
            else:
                p_even.next = p
                p_even = p
            p = p.next
            flag = not flag
        p_odd.next = even_head.next
        p_even.next = None
        return odd_head.next
        


发表于 2023-07-20 23:05:18 回复(0)
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)
public ListNode oddEvenList (ListNode head) {
        //空 一个 两个节点 直接返回
        if(head==null||head.next==null||head.next.next==null)
            return head;

        ListNode snd = head.next;//偶数头
        ListNode cur1 = head;//处理奇数节点
        ListNode cur2 = snd;//处理偶数节点
        
        while(cur1!=null&&cur2!=null){//奇数连接、偶数连接
            cur1.next = cur2.next;
            if(cur2.next==null) break;
            cur1 = cur2.next;
            cur2.next = cur1.next;
            cur2 = cur1.next;
        }
    
        cur1.next = snd;//奇数尾连接偶数头
        return head;
    }

发表于 2023-03-12 19:33:45 回复(0)
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        if(head == NULL || head -> next == NULL) return head;
        
        ListNode *p = head, *q = head -> next;
        int cnt = 0;
        while(p)
        {
            cnt++;
            p = p -> next;
        }
        p = head;

        if(cnt % 2 == 0)
        {
            while(q -> next)
            {
                ListNode *r = q -> next;
                q -> next = r -> next;
                r -> next = p -> next;
                p -> next = r;
                p = r;
                q = q -> next;
            }
        }
        else 
        {
            while(q)
            {
                ListNode *r = q -> next;
                q -> next = r -> next;
                r -> next = p -> next;
                p -> next = r;
                p = r;
                q = q -> next;
            }
        }
        
        
        return head;
    }
};

发表于 2023-02-10 12:33:44 回复(0)
双指针,交替行走,重点在于什么时候出循环?A:易见,每循环一次,p2在p1之后一个位置(原链表中),因此当p2为nullptr或p2为最后一个元素时结束。
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* h1 = head, *h2 = head->next;
        ListNode* p1 = h1, *p2 = h2;
        while(p2 && p2->next) {

            p1 = p1 ? (p1->next ? p1->next = p1->next->next : p1) : p1;
            p2 = p2 ? (p2->next ? p2->next = p2->next->next : p2) : p2;
        }
        p1->next = h2;
        return h1;
    }
};

发表于 2022-12-24 00:00:32 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) 
    {
        if(head == nullptr)
        {
            return head;
        }
        ListNode *p = head,*q = head->next,*tow = head->next;
        while(p->next && q->next)
        {
            p->next = p->next->next;
            q->next = q->next->next;
            p = p->next;
            q = q->next;
        }
        p->next = tow;
        return head;
     }
};

发表于 2022-11-02 21:10:36 回复(0)