首页 > 试题广场 >

链表的奇偶重排

[编程题]链表的奇偶重排
  • 热度指数：104033 时间限制：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
狂野的小狮子头像 狂野的小狮子 
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)
Java
呸看见你就开心头像 呸看见你就开心 
import java.util.*;
public class Solution {
    public ListNode oddEvenList (ListNode head) {
        if (head == null) {
            return null;
        }
        //phead1 phead2 分别存储奇数位结点和偶数位结点
        //p1 p2分别遍历两个链表，最后第一个链表的最后连接第二个链表的开始
        ListNode phead1 = new ListNode(-1);
        ListNode p1 = phead1;
        ListNode phead2 = new ListNode(-1);
        ListNode p2 = phead2;
        ListNode cur = head;
        int idx = 1;
        ListNode tmp;
        while (cur != null) {
            tmp = cur;
            cur = cur.next;
            tmp.next = null;
            if (idx % 2 == 1) {
                p1.next = tmp;
                p1 = p1.next;
            } else {
                p2.next = tmp;
                p2 = p2.next;
            }
            idx++;
        }
        p1.next = phead2.next;
        return phead1.next;
    }
}

发表于 2023-03-21 23:10:05 回复(0)
Java
牛客363828470号头像 牛客363828470号 
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)
Java
牛客585981974号头像 牛客585981974号 
public class Solution {
    public ListNode oddEvenList (ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode start1 = head;
        ListNode start2 = head.next;
        ListNode temp1 = start1;
        ListNode temp2 = start2;
        while(start2 != null && start2.next != null){
            start1.next = start1.next.next;
            start2.next = start2.next.next;
            start1 = start1.next;
            start2 = start2.next;
        }
        start1.next = temp2;
        return temp1;
    }
}

发表于 2023-02-03 11:43:23 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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