首页 > 试题广场 >

排序奇升偶降链表

[编程题]排序奇升偶降链表

热度指数：2275 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个奇数位升序，偶数位降序的链表，返回对其排序后的链表。

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

数据范围：链表中元素个数满足 $1 \le n \le 10000 \$ ，链表中的元素大小满足 $1 \le val \le 100000 \$

示例1

输入

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

输出

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

示例2

输入

{1,2,2}

输出

{1,2,2}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Java

菜鸡真的不配有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

简简单单

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

直接对链表进行排序的话至少也需要O(nlogn)的时间复杂度，我们注意到链表的奇数位和偶数位其实是有序的，而要将两个有序的部分变为整体有序，归并是再适合不过的了。因此我们可以按照如下的算法来求解：

先将链表的拆成奇数位和偶数位两条链表，时间复杂度O(n)；
再将偶数位链表进行反转，时间复杂度O(n)；
最后归并两个升序的链表，时间复杂度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)