首页 > 试题广场 >

链表的奇偶重排

[编程题]链表的奇偶重排
  • 热度指数：121908 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
Java
key7520头像 key7520 
public ListNode oddEvenList (ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode curr1 = head;
        ListNode curr2 = curr1.next;
        ListNode head2 = curr2;
        while(curr2!=null){
            curr1.next = curr2.next;
            if(curr1.next == null) break;
            curr1 = curr1.next;
            curr2.next = curr1.next;
            curr2 = curr1.next;
        }
        curr1.next = head2;
        return dummy.next;
    }


发表于 2025-06-10 21:58:16 回复(0)
Java
୧⍢⃝୨头像 ୧⍢⃝୨ 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode p1 = head;
        ListNode p2 = head.next;
        ListNode startNode1 = head;
        ListNode startNode2 = head.next;

        while (p2 != null) {
            p1.next = p2.next;
            p1 = p2;
            p2 = p2.next;
        }

        p1 = startNode1;
        while (p1.next != null) {
            p1 = p1.next;
        }

        p1.next = startNode2;
        return startNode1;
    }
}

发表于 2024-09-10 14:35:54 回复(0)
Java
牛客348570162号头像 牛客348570162号 
public ListNode oddEvenList (ListNode head) {
        ListNode head1 = new ListNode(999);
        ListNode head2 = new ListNode(999);
        ListNode pre1 = head1,pre2 = head2;
        int i = 0;
        while(head != null){
            if(i % 2 == 0){
                pre1.next = head;
                pre1 = pre1.next;
            }else{
                pre2.next = head;
                pre2 = pre2.next;
            }
            head = head.next;
            i++;
        }
        pre2.next = null;
        pre1.next = head2.next;
        return head1.next;
    }

发表于 2024-08-20 11:20:25 回复(0)
Java
人间水长东头像 人间水长东 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here

        // 使用容器做中转，要求：有序，如：队列

        // 算法的时间复杂度O(N)，额外空间复杂度O(N)

        // 1.处理特殊链表
        if(head == null || head.next == null || head.next.next == null) {
            // 如果该链表无结点、单节点、双节点，直接返回
            return head;
        }

        // 2.第一遍遍历链表，按照下标的奇数和偶数分别存入不同的Queue中
        Queue<ListNode> oddList = new LinkedList<>();
        Queue<ListNode> evenList = new LinkedList<>();
        ListNode cur = head;
        int i = 0;
        while (cur != null) {
            i++;
            if (i % 2 == 1) {
                // 奇数位置，放入oddList集合中
                oddList.add(cur);
            } else {
                // 偶数位置，放入evenList集合中
                evenList.add(cur);
            }
            cur = cur.next;
        }

        // 3.先后从两个LinkedList中取出数据，奇集合在前，偶集合在后
        ListNode oddHead = null;
        ListNode oddTail = null;
        ListNode evenHead = null;
        ListNode evenTail = null;
        // 3.1 构建奇数位置结点链表
        while(!oddList.isEmpty()) {
            ListNode oddCur = oddList.poll();
            // 注意！结点出队后应该让其next指向null，避免可能的错误
            oddCur.next = null;
            if(oddHead == null) {
                // 第一次尾插新结点
                oddHead = oddCur;
                oddTail = oddHead;
            } else {
                oddTail.next = oddCur;
                oddTail = oddCur;
            }
        }
        // 3.2 构建偶数位置结点链表
        while(!evenList.isEmpty()) {
            ListNode evenCur = evenList.poll();
            // 注意！结点出队后应该让其next指向null，避免可能的错误
            evenCur.next = null;
            if(evenHead == null) {
                // 第一次尾插新结点
                evenHead = evenCur;
                evenTail = evenHead;
            } else {
                evenTail.next = evenCur;
                evenTail = evenCur;
            }
        }

        // 4.把它们连到一起，返回
        oddTail.next = evenHead;
        return oddHead;
    }
}

发表于 2024-07-27 11:55:08 回复(0)
Java
狂野的小狮子头像 狂野的小狮子 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }

        ListNode temp = head;
        ListNode pre = head.next, p;

        while (pre != null && pre.next != null) {
            p = pre.next;
            pre.next = p.next;
            p.next = temp.next;
            temp.next = p;
            temp = p;
            pre = pre.next;
        }

        return head;
    }
}

发表于 2024-06-11 14:38:08 回复(0)
Java
木3吉吉头像 木3吉吉 
import java.util.*;


public class Solution {

    public ListNode oddEvenList (ListNode head) {
        // write code here
        if(head == null)
            return null;
        if(head.next == null){
            return head;
        }
        //记录奇数位置的链表表头
        ListNode oddHead = head;
        //记录偶数位置的链表表头
        ListNode evenHead = head.next;

        //双指针遍历链表进行跳跃连接，遍历到最后将原始链表分为两个链表，且最后的节点为cur和mid
        ListNode cur = head;
        ListNode mid = head.next;

        while(mid.next != null){
            ListNode mid_next = mid.next;
            //当前节点指向下下个节点
            cur.next = mid_next;
            //双指针后移
            cur = mid;
            mid = mid_next;
        }
        //最后设为null，分成两个链表，mid已经指向null
        cur.next = null;

        //根据原始链表的个数的奇偶性不同判断evenHead链表的最后一个节点是cur还是mid
        ListNode temp = evenHead;
        while(temp.next != null){
            temp = temp.next;
        }
        //连接奇链表和偶链表
        if(temp == cur){//cur指针作为even链表的最后指针 
            mid.next = evenHead;
        }else{//mid指针最为even链表的最后指针
            cur.next = evenHead;
        }
        return oddHead;
    }
}

发表于 2024-05-22 17:50:44 回复(0)
Java
牛客839384289号头像 牛客839384289号 
public ListNode oddEvenList (ListNode head) {
    // write code here
    ListNode p1=new ListNode(0) ,p3=p1;
    ListNode p2=new ListNode(0) ,p4=p2;
    boolean flag=true;
    while(head!=null){
        if(flag){
            p3.next=head;
            p3=p3.next;
        }else{
            p4.next=head;
            p4=p4.next;
        }
        head=head.next;
        flag=!flag;
    }
    p3.next=p2.next;
    p4.next=null;
    return p1.next;
}

发表于 2024-03-03 15:59:52 回复(0)
Java
在努力的李子头像 在努力的李子
public static ListNode oddEvenList (ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode odd = head; //奇数链标指针
        ListNode even = head.next;//偶数链表指针
        ListNode evenHead = even;

        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }//最后odd指向奇数最后一个 even指向偶数最后一个（偶数个）或null（奇数个）
        odd.next = evenHead;
        return head;


    }

发表于 2023-11-22 23:23:04 回复(0)
Java
serein_kk头像 serein_kk 
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if (head == null) {
            return null;
        }
        int cnt = 1;
        ListNode dummyj = new ListNode(0);
        ListNode dummyo = new ListNode(0);
        ListNode p1 = dummyj, p2 = dummyo, p = head;
        while (p != null) {
            if (cnt % 2 != 0) {
                p1.next = p;
                p1 = p1.next;
            } else {
                p2.next = p;
                p2 = p2.next;
            }
            p = p.next;
            cnt += 1;
        } 
        p1.next = dummyo.next;
        p2.next = null;
        return dummyj.next;
    }
发表于 2023-11-09 20:03:06 回复(0)
Java
牛客365729973号头像 牛客365729973号
是不是bug了
发表于 2023-11-03 11:12:40 回复(0)
Java
求知心态头像 求知心态 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        if (head==null||head.next==null||head.next.next==null){
            return head;
        }
        ListNode odd = new ListNode(head.val), even = new ListNode(head.next.val);
        ListNode left = odd, right = even, oddNext = null, evenNext = null;
        int index = 2;
        head = head.next.next; //3
        while (head != null) {
            index++;
            if (index % 2 == 1) {
                oddNext = new ListNode(head.val);
                odd.next = oddNext;
                odd = odd.next;
            } else {
                evenNext = new ListNode(head.val);
                even.next = evenNext;
                even = even.next;
                if (head.next == null) {
                    even.next = null;
                }
            }
            head = head.next;
        }
        odd.next = right;
        return left;
    }
}

发表于 2023-10-19 21:44:20 回复(0)
Java
dqxfz头像 dqxfz
    public ListNode oddEvenList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode oddHead = head, evenHead = head.next, oh = oddHead, eh = evenHead;
        head = head.next.next;
        oh.next = eh.next = null;
        int i = 1;
        while (head != null) {
            // 对2求余，为0则是偶数，为1则是奇数
            if ((i & 1) == 0) {
                eh.next = head;
                eh = eh.next;
                head = head.next;
                eh.next = null;
            } else {
                oh.next = head;
                oh = oh.next;
                head = head.next;
                oh.next = null;
            }
            i++;
        }
        oh.next = evenHead;
        return oddHead;
    }
发表于 2023-09-13 15:08:10 回复(0)
Java
最美不过初见2头像 最美不过初见2 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        ListNode even=new ListNode(-1);
        ListNode e=even;
        ListNode odd=new ListNode(-1);
        ListNode o=odd;
        int count=0;
        ListNode p=head;
        while(p!=null){
            count++;
            if(count%2==0){
                ListNode tmp=p.next;
                o.next=p;
                p.next=null;
                o=p;
                p=tmp; 
            }else{
               ListNode tmp=p.next;
                e.next=p;
                p.next=null;
                e=p;
                p=tmp;     
            }
        }
        e.next=odd.next;
        return even.next;
    }
}

发表于 2023-09-12 12:50:56 回复(0)
Java
牛客781396821号头像 牛客781396821号 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        // 注意没有元素、只有1个元素、只有两个元素的情况
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode l1 = head;
        ListNode l1h = head;
        ListNode l2 = head.next;
        ListNode l2h = head.next;
        while (true) {
            l1.next = l2.next;
            l1 = l1.next;
            if (l1.next == null) break;
            l2.next = l1.next;
            l2 = l2.next;
            if (l2.next == null) break;
        }

        l1.next = l2h;
        // 注意l2的next要设为null，避免循环出现
        l2.next = null;
        ListNode l1h1 = l1h;
        return l1h;
    }
}
发表于 2023-08-19 19:08:26 回复(0)
Java
Kanodayo头像 Kanodayo 
public ListNode oddEvenList (ListNode head) {
        // write code here
        ListNode result = null;
        if(head==null||head.next==null){
            return head;
        }
        ListNode oddlist = head, evenlist = head.next, temp = head.next.next;
        result=oddlist;
        ListNode evenhead=evenlist;
        while(temp!=null&&temp.next!=null){
            oddlist.next=temp;
            oddlist=oddlist.next;
            temp=temp.next;
            evenlist.next=temp;
            evenlist=evenlist.next;
            temp=temp.next;
        }
        if(temp!=null){
            oddlist.next=temp;
            oddlist=oddlist.next;
            evenlist.next=null;
        }
        oddlist.next=evenhead;

        return result;
    }

发表于 2023-08-08 16:53:30 回复(0)
Java
菲菲菲12138头像 菲菲菲12138
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if(head==null){
            return null;
        }
        List<Integer> list1=new ArrayList<Integer>();
        List<Integer> list2=new ArrayList<Integer>();
        ListNode cur=head;
        int num=0;
        while(cur!=null){
            num++;
            if(num%2!=0){
                list1.add(cur.val);
            }else{
                list2.add(cur.val);
            }
            cur=cur.next;
        }
        ListNode res=new ListNode(-1);
        res.next=null;
        ListNode r=res;
        for(int i=0;i<list1.size();i++){
            ListNode node=new ListNode(list1.get(i));
            r.next=node;
            r=r.next;
        }
        for(int j=0;j<list2.size();j++){
              ListNode node=new ListNode(list2.get(j));
              r.next=node;
              r=r.next;
        }

        return res.next;
    }
发表于 2023-07-20 09:47:15 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public ListNode oddEvenList (ListNode head) {
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        if(head==null) return null;
        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 dummy.next;       
    }

发表于 2023-07-19 09:12:41 回复(0)
Java
抓住努力的尾巴头像 抓住努力的尾巴 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        //判断 head == null
        if (head == null) {
            return null;
        }
        int count = 0;

        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;

        while (cur != null) {
            count++;
            if (count % 2 != 0) {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            } else {
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        be.next = as;
        if(as != null) {
            ae.next = null;
        }
        return bs;
    }
}
发表于 2023-07-10 12:59:30 回复(0)
Java
SUMMERENT头像 SUMMERENT 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        ArrayList<Integer> list3 = new ArrayList<>();
        while (head != null) {
             list1.add(head.val);
            if(head.next!=null){ 
                head = head.next; 
                list2.add(head.val); 
            }
            head = head.next; 
        }
        list3.addAll(list1);
        list3.addAll(list2);
        ListNode sen = new ListNode(-1);
        ListNode cur = sen;
        for (int i = 0; i < list3.size(); i++) {
            cur.next = new ListNode(list3.get(i));
            cur = cur.next;
        }
        return sen.next;
    }
}

发表于 2023-03-23 10:56:52 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

链表的奇偶重排

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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