首页 > 试题广场 >

排序奇升偶降链表

[编程题]排序奇升偶降链表
  • 热度指数：3181 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个奇数位升序，偶数位降序的链表，返回对其排序后的链表。

题面解释：例如链表 1->3->2->2->3->1 是奇数位升序偶数位降序的链表，而 1->3->2->2->3->2 则不符合题目要求。

数据范围：链表中元素个数满足 ，链表中的元素大小满足
示例1

输入

{1,3,2,2,3,1}

输出

{1,1,2,2,3,3}
示例2

输入

{1,2,2}

输出

{1,2,2}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
FieldMatching头像 FieldMatching 
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 sortLinkedList (ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        // 1.分离奇偶链表
        ListNode evenHead = evenList(head);
        // 2.翻转偶数链表
        ListNode head2 = reverse(evenHead);
        // 3.合并两个有序链表
        return merge(head, head2);
    }

    private ListNode evenList(ListNode head) {
        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 = null;
        return evenHead;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode after = curr.next;
            curr.next = prev;
            prev = curr;
            curr = after;
        }
        return prev;
    }

    private ListNode merge(ListNode p, ListNode q) {
        ListNode sentinel = new ListNode(-1);
        ListNode curr = sentinel;
        while (p != null && q != null) {
            if (p.val < q.val) {
                curr.next = p;
                p = p.next;
            } else {
                curr.next = q;
                q = q.next;
            }
            curr = curr.next;
        }
        curr.next = p != null ? p : q;
        return sentinel.next;
    }
}

发表于 2025-10-07 16:58:33 回复(0)
Java
Sen🍓🍀头像 Sen🍓🍀 
import java.util.*;

public class Solution {

    public ListNode sortLinkedList (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;

        // 挑出奇偶链表
        ListNode oddHead = head, evenHead = head.next;
        ListNode oddPre = head, evenPre = evenHead, odd, even;
        while (evenPre != null) {
            if (evenPre.next == null) {
                oddPre.next = null;
                break;
            }
            odd = evenPre.next;
            even = odd.next;
            oddPre.next = odd;
            oddPre = odd;
            evenPre.next = even;
            evenPre = even;

        }
        // 反转偶链表
        evenPre = null;
        even = evenHead;
        while (even != null) {
            ListNode evenNext = even.next;
            even.next = evenPre;
            evenPre = even;
            even = evenNext;
        }
        evenHead = evenPre;
        // 合并奇偶链表
        ListNode res = new ListNode(-1), p = res;
        while (oddHead != null && evenHead != null) {
            if (oddHead.val < evenHead.val) {
                p.next = oddHead;
                oddHead = oddHead.next;
                p = p.next;
            } else {
                p.next = evenHead;
                evenHead = evenHead.next;
                p = p.next;
            }
        }
        if (oddHead != null) p.next = oddHead;
        if (evenHead != null) p.next = evenHead;

        return res.next;
    }
}

发表于 2025-04-03 09:55:17 回复(0)
Java
菜鸡真的不配有offer头像 菜鸡真的不配有offer 
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 sortLinkedList (ListNode head) {
        // write code here
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode head2 = head.next;
        ListNode cur1 = head;
        ListNode cur2 = head2;
        ListNode dummy = new ListNode(-1);
        
        while (cur1 != null && cur2 != null && cur2.next != null) {
            ListNode next1 = cur2.next;
            ListNode next2 = cur2.next.next;
            cur1.next = next1;
            cur2.next = next2;
            cur1 = next1;
            cur2 = next2;
        }
        cur1.next = null;
        // reverse list
        ListNode newHead = reverse(head2);
        // merge list
        return mergeList(head, newHead);
    }

    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    private ListNode mergeList(ListNode t1, ListNode t2) {
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        while (t1 != null && t2 != null) {
            if (t1.val <= t2.val) {
                pre.next = t1;
                pre = t1;
                t1 = t1.next;
            } else {
                pre.next = t2;
                pre = t2;
                t2 = t2.next;
            }
        }
        pre.next = t1 != null ? t1 : t2;
        return dummy.next;
    }
}

编辑于 2024-02-15 13:04:14 回复(0)
Java
傻狍子d头像 傻狍子d

简简单单

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode sortLinkedList (ListNode head) {
        // write code here
        //1. 奇数一条链表, 偶数一条链表
        if(head == null || head.next == null)return head;

        ListNode l1 = head;
        ListNode l2 = head.next;

        ListNode odd = head;
        ListNode even = head.next;

        while(true){
            if(even == null || even.next == null)break;

            odd.next = even.next;
            odd = odd.next;

            even.next = odd.next;
            even = even.next;
        }
        odd.next = null;
        //2. 翻转偶数链表
        l2 = reverse(l2);
        //3. 合并奇偶两条链表
        return  merge(l1, l2);
    }
    public ListNode reverse(ListNode head){
        ListNode cur = head;
        ListNode pre = null;

        while(true){
            if(cur == null)break;

            ListNode cur_next = cur.next;

            cur.next = pre;

            pre = cur;
            cur = cur_next;

        }
        return pre;
    }

    public ListNode merge(ListNode l1, ListNode l2){
        if(l1 == null || l2 == null)return l1 == null ? l2 : l1;

        if(l1.val <= l2.val){
            l1.next = merge(l1.next, l2);
            return l1;
        }else{
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}
发表于 2022-07-25 23:37:41 回复(0)
Java
橘子不剥皮头像 橘子不剥皮 
public ListNode sortLinkedList (ListNode head) {
        // write code here
        if(head == null||head.next==null)return head;
        
        
        ListNode cur = head.next.next;
        
        ListNode l1 = head;
        ListNode l2 = head.next;
        ListNode dl1 = l1;
        ListNode dl2 = l2;
        int count = 1;
        while(cur!=null){
          
            if(count % 2 == 0){
                l2.next = cur;
                l2 = l2.next;
            }else{
                l1.next = cur;
                l1 = l1.next;
            }
            cur = cur.next;
            count++;
            
        }
        l1.next = null;
        l2.next = null;
        dl2 = reverse(dl2);
        
        return mergeTwoLists(dl1,dl2);
        
        
    }
    
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null&&list2==null)return null;
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;


        while (list1!=null&&list2!=null){
            if(list1.val<list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1==null)cur.next = list2;
        if(list2==null)cur.next = list1;

        return dummyHead.next;
    }
    
    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
        
    }

发表于 2022-04-13 17:19:44 回复(0)
Java
pein531头像 pein531
直接对链表进行排序的话至少也需要O(nlogn)的时间复杂度，我们注意到链表的奇数位和偶数位其实是有序的，而要将两个有序的部分变为整体有序，归并是再适合不过的了。因此我们可以按照如下的算法来求解：
  1. 先将链表的拆成奇数位和偶数位两条链表，时间复杂度O(n)；
  2. 再将偶数位链表进行反转，时间复杂度O(n)；
  3. 最后归并两个升序的链表，时间复杂度O(n)。
算法的整体时间复杂度是O(n)，只使用了有限几个变量，空间复杂度为O(1)。 
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 sortLinkedList (ListNode head) {
        // write code here
        if(head == null || head.next == null) return head;
        // 先把奇数位链表和偶数位链表拆开
        ListNode oddCur = head;
        ListNode evenCur = oddCur.next;
        ListNode oddHead = oddCur;
        ListNode evenHead = evenCur;
        while(evenCur != null){
            oddCur.next = evenCur.next;
            if(oddCur.next != null)
                evenCur.next = oddCur.next.next;
            oddCur = oddCur.next;
            evenCur = evenCur.next;
        }
        // 然后把偶数位链表逆序
        evenHead = reverseList(evenHead);
        // 最后把两个升序的链表归并
        return mergeList(oddHead, evenHead);
    }
    
    // 反转链表
    private ListNode reverseList(ListNode head) {
        if(head == null) return head;
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    
    // 合并两个有序链表
    private ListNode mergeList(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(head1 != null && head2 != null){
            if(head1.val <= head2.val){
                cur.next = head1;
                head1 = head1.next;
            }else{
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        while(head1 != null){
            cur.next = head1;
            head1 = head1.next;
            cur = cur.next;
        }
        while(head2 != null){
            cur.next = head2;
            head2 = head2.next;
            cur = cur.next;
        }
        return dummy.next;
    }
}

发表于 2021-12-14 10:10:40 回复(0)
提交观点

问题信息

链表
难度：
6条回答 5104浏览

热门推荐

通过挑战的用户

查看代码

相关试题

排序奇升偶降链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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