首页 > 试题广场 >

排序奇升偶降链表

[编程题]排序奇升偶降链表
  • 热度指数：2701 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
C++
Getchance头像 Getchance 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* sortLinkedList(ListNode* head) {
        // write code here
        if(!head||!head->next) return head;
        ListNode* l1=new ListNode(-1),*l2=new ListNode(-2);
        ListNode* t1=l1,*t2=l2;
        ListNode* mv=head;
        int count=0;
        while(head){
            count++;
            if(count%2!=0){
                l1->next=head;
                l1=l1->next;
            }
            else{
                l2->next=head;
                l2=l2->next;
            }
            head=head->next;
        }
        l1->next=nullptr,l2->next=nullptr;
        
        l1=t1->next,l2=reverse(t2->next);
        return merge(l1, l2);
    }
    
    ListNode* reverse(ListNode* head){ //反转链表
        if(!head) return head;
        ListNode* node=nullptr;
        while(head){
            ListNode* tmp=head->next;
            head->next=node;
            node=head;
            head=tmp;
        }
        return node;
    }
    ListNode* merge(ListNode* l1,ListNode* l2){ //合并有序链表
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val<l2->val){
            l1->next=merge(l1->next,l2);
            return l1;
        }
        l2->next=merge(l1,l2->next);
        return l2;
    }
};

发表于 2022-07-25 10:58:14 回复(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)
空中转体一周半头像 空中转体一周半

三步法：1.拆分奇偶链表。2.逆序偶链表。3.合并两链表

import java.util.*;
public class Solution {
    public ListNode sortLinkedList (ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode odd = head;
        ListNode even = head.next;
        head = even.next;
        even.next = null;
        ListNode p = even;
        ListNode q = odd;
        while(head != null) {
            q.next = head;
            head = head.next;
            q = q.next;
            q.next = null;
            if(head != null) {
                p.next = head;
                head = head.next;
                p = p.next;
                p.next = null;
            }
        }
        return merge(odd, reverse(even));
    }
    public ListNode merge(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null)return list1;
        if(list1.val > list2.val) {
            list2.next = merge(list1, list2.next);
            return list2;
        }
        list1.next = merge(list1.next, list2);
        return list1;
    }
    public ListNode reverse(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode p = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}
发表于 2023-05-23 11:00:14 回复(0)
唐氏综合征头像 唐氏综合征
分三步：

第一步： 拆分为奇偶链表：
第二步：将偶数链表翻转，使得其升序
第三步：合并两个链表，按照 val 值升序排列 
 public static ListNode sortLinkedList(ListNode head) {
        // write code here
        ListNode tmp = head;
        ListNode ji = tmp;
        ListNode ou = ji.next;
        // split two node
        while (tmp.next != null) {
            ListNode nextTmp = tmp.next;
            tmp.next = nextTmp.next;
            tmp = nextTmp;
        }
        // 合并
        return mergeTwoSortedNodeList(ji,reverse(ou));
    }

    // 合并两个排序后的链表

    public static ListNode mergeTwoSortedNodeList(ListNode l1, ListNode l2) {
        ListNode preNode = new ListNode(-1);
        // 用于合并链表
        ListNode tmpNode = preNode;
        // 遍历两个链表，直到其中一个为空
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tmpNode.next = l1;
                l1 = l1.next;
            } else {
                tmpNode.next = l2;
                l2 = l2.next;
            }
            tmpNode = tmpNode.next;
        }

        // 处理剩余的节点
        tmpNode.next = l1 != null ? l1 : l2;

        // 返回合并后的链表（跳过哑节点）
        return preNode.next;
    }

    private static ListNode reverse(ListNode node) {
        if (node == null) return null;
        ListNode prev = null;
        ListNode curr = node;

        while (curr != null) {
            ListNode nextTmp = curr.next;
            curr.next = prev;
            // 准备下一轮
            prev = curr;
            curr = nextTmp;
        }
        return prev;
    }



发表于 2024-07-25 16:56:17 回复(0)
C++
zhangbw_头像 zhangbw_

  1. 头插法奇偶节点分离

  2. 有序链表归并

    class Solution {
public:
 ListNode* sortLinkedList(ListNode* head) {
     if (head == nullptr || head->next == nullptr) return head;
     ListNode* dummy = new ListNode(-1), *p = head;

     // 头插法奇偶分离
     while (p && p->next) {
         ListNode* u = p->next;
         p->next = u->next;
         u->next = dummy->next;
         dummy->next = u;
         p = p->next;
     }

     // 有序链表归并
     ListNode* ans = new ListNode(-1), *cur = ans;
     p = dummy->next;
     while (head && p) {
         if (head->val <= p->val) {
             cur->next = head;
             head = head->next;
         } else {
             cur->next = p;
             p = p->next;
         }
         cur = cur->next;
     }
     head == nullptr ? cur->next = p : cur->next = head;
     return ans->next;
 }
};
发表于 2023-04-18 13:39:40 回复(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)
Go
今天无bug_头像 今天无bug_ 
func sortLinkedList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var jishu []int
	var oushu []int
	num := 1
	for head != nil {
		if num%2 == 0 {
			oushu = append(oushu, head.Val)
		} else {
			jishu = append(jishu, head.Val)
		}
		head = head.Next
		num++
	}

	sort.Slice(jishu, func(i, j int) bool {
		return jishu[i] < jishu[j]
	})
	sort.Slice(oushu, func(i, j int) bool {
		return oushu[i] > oushu[j]
	})

	var ret []int
	for i := 0; i < len(jishu); i++ {
		ret = append(ret, jishu[i])
		if i < len(oushu) {
			ret = append(ret, oushu[i])
		}
	}
	var retNode *ListNode
	p := retNode
	for _, val := range ret {
		if retNode == nil {
			retNode = &ListNode{Val: val}
			p = retNode
		} else {
			retNode.Next = &ListNode{Val: val}
			retNode = retNode.Next
		}
	}
	return p
}


发表于 2025-03-25 15:29:19 回复(0)
17c89头像 17c89 
import java.util.*;

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

/**
 * NC207 排序奇升偶降链表
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 头插法 + 尾插法 + 递归合并
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode sortLinkedList (ListNode head) {
        ListNode oddHead = new ListNode(-1);
        ListNode evenHead = new ListNode(-1);

        ListNode odd,even,oddTail;
        oddTail = oddHead;
        odd = head;
        while(odd != null){
            even = odd.next;
            // 尾插法 <- 已经升序
            odd.next = null;
            oddTail.next = odd;
            oddTail = odd;

            if(even == null){
                break;
            }

            odd = even.next;
            // 头插法 <- 转成升序
            even.next = evenHead.next;
            evenHead.next = even;
        }

        return merge(oddHead.next, evenHead.next);
    }
    
    /**
     * 合并
     *
     * 合并两个升序链表(奇偶)
     *
     * @param odd
     * @param even
     * @return
     */
    private ListNode merge(ListNode odd, ListNode even){
        if(odd == null){
            return even;
        }
        if(even == null){
            return odd;
        }

        if(odd.val < even.val){
            odd.next = merge(odd.next, even);
            return odd;
        }else{
            even.next = merge(odd, even.next);
            return even;
        }
    }
}

发表于 2024-12-28 21:22:07 回复(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)
甘雨刻晴头像 甘雨刻晴
  1. 分离奇偶节点
  2. 翻转偶节点链表
  3. 合并两个有序链表

这个题在分离奇偶节点时切勿直接在链表上进行操作，通过index记录当前节点的奇偶性，可以减少复杂度，面试时也不容易出错。

今天面试时写了个分离过程中翻转偶节点还没用index，直接用的next->next这样写的，差点翻车。。。

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    ListNode* merge(ListNode* h1, ListNode* h2) {
        ListNode* newHead = new ListNode(0);
        ListNode* curr = newHead;
        while (h1 && h2) {
            if (h1->val < h2->val) {
                curr->next = h1;
                h1 = h1->next;
            } else {
                curr->next = h2;
                h2 = h2->next;
            }
            curr = curr->next;
        }
        curr->next = h1 ? h1 : h2;
        return newHead->next;
    }

    ListNode* sortLinkedList(ListNode* head) {
        // write code here
        ListNode* oddHead = new ListNode(0);
        ListNode* evenHead = new ListNode(0);
        ListNode* odd = oddHead, *even = evenHead;
        int index = 1;
        ListNode* curr = head;
        while(curr) {
            if(index % 2 == 1) {
                odd->next = curr;
                odd = odd->next;
            }else{
                even->next = curr;
                even = even->next;
            }
            index++;
            curr = curr->next;
        }
        odd->next = nullptr;
        even->next = nullptr;
        evenHead = reverse(evenHead->next);
        return merge(oddHead->next, evenHead);
    }
};
发表于 2023-03-17 16:18:07 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main

import "sort"
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
*/
func sortLinkedList( head *ListNode ) *ListNode {
    arr:=[]*ListNode{}
    for p:=head;p!=nil;p=p.Next{
        arr=append(arr,p)
    }
    sort.Slice(arr,func(i,j int)bool{
        return  arr[i].Val<arr[j].Val
    })
    for i,ln:=range arr{
        if i+1<len(arr){
            ln.Next=arr[i+1]
        }else{
            ln.Next=nil
        }
    }
    return arr[0]
}

发表于 2023-03-08 18:43:23 回复(0)
孤独时代的罗永浩头像 孤独时代的罗永浩 
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
        ListNode dummy=new ListNode(-1);
        ListNode tail=dummy;
        ListNode dummy1=new ListNode(-1);
        ListNode tail1=dummy1;
        ListNode dummy2=new ListNode(-1);
        ListNode tail2=dummy2;
        ListNode a=head;
        for(;a!=null;){
            if(a!=null){
                tail1=tail1.next=a;
                a=a.next;
            }
            if(a!=null){
                tail2=tail2.next=a;
                a=a.next;
            }
        }
        tail1.next=null;
        tail2.next=null;
        a=null;
        ListNode b=dummy2.next;
        for(;b!=null;){
            ListNode c=b.next;
            b.next=a;
            a=b;
            b=c;
        }
        dummy2.next=a;
        ListNode i=dummy1.next,j=dummy2.next;
        while(i!=null&&j!=null){
            if(i.val<j.val){
                tail=tail.next=i;
                i=i.next;
            }else{
                tail=tail.next=j;
                j=j.next;
            }
        }
        while(i!=null){
            tail=tail.next=i;
            i=i.next;
        }
        while(j!=null){
            tail=tail.next=j;
            j=j.next;
        }
        tail.next=null;
        return dummy.next;
    }
}

发表于 2023-01-24 16:13:24 回复(0)
腰马合一小垃圾头像 腰马合一小垃圾 
public ListNode sortLinkedList (ListNode head) {
        // write code here
        if(head == null || head.next == null){
            return head;
        }
        ListNode oddHead = new ListNode(-1);
        ListNode oddTail = oddHead;
        ListNode evenHead = new ListNode(-1);
        ListNode evenTail = evenHead;
        ListNode cur = head;
        int index = 0;
        while(cur != null){
            ++index;
            if((index & 1) == 1){
                oddTail.next = new ListNode(cur.val);
                oddTail = oddTail.next;
            }else {
                evenTail.next = new ListNode(cur.val);
                evenTail = evenTail.next;
            }
            cur = cur.next;
        }
        return(merge(oddHead.next, reverse(evenHead.next)));
    }

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

    private ListNode merge(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;
        }
        cur.next = head1 == null ? head2 : head1;
        return dummy.next;
    }

发表于 2023-01-07 20:21:06 回复(0)
C++
AsherChi头像 AsherChi 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* sortLinkedList(ListNode* head) {
        // write code here
       vector<int> ou, odd;
        int i = 0;
        while(head)
        {
            if(i % 2 == 0)
                odd.push_back(head->val);
            else
                ou.push_back(head->val);
//             val.push_back(head->val);
            i++;
            head = head->next;
        }
        int n2 = ou.size(), n1 = odd.size();
        int j = n2 - 1;
        i = 0;
        ListNode* node = new ListNode(-1);
        ListNode* cur = node;
        while(i < n1 && j>=0)
        {
            if(ou[j] < odd[i])
            {
                ListNode* tmp =new ListNode(ou[j--]);
                cur->next = tmp;
            }
            else
            {
                ListNode* tmp = new ListNode(odd[i++]);
                cur ->next = tmp;
            }
            cur=cur->next;
        }
        while(i<n1)
        {
            ListNode* tmp = new ListNode(odd[i++]);
            cur->next = tmp;
            cur = cur->next;
        }
        while(j>=0)
        {
            ListNode* tmp = new ListNode(ou[j--]);
            cur->next = tmp;
            cur = cur->next;
        }
        return node->next;
    }
};

发表于 2022-09-04 11:04:13 回复(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)
Nacylin头像 Nacylin
Python解法：
三步走：
class Solution:
    def sortLinkedList(self , head: ListNode) -> ListNode:
        # write code here
        # 排除为空和单个情况
        if not head or not head.next:
            return head    
        odd = oddHead =  head
        even = evenHead =head.next
        while even:
            odd.next = even.next
            if odd.next:
                even.next = odd.next.next
            odd = odd.next
            even = even.next
        # 把偶数位链表逆序
        evenHead = self.reveseList(evenHead)
        # 最后把两个升序的链表归并
        return self.SorttwoList(oddHead, evenHead)
    def reveseList(self,head):
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre
    # 合并两个链表
    def SorttwoList(self,l1,l2):
        dummy = ListNode(-1)
        cur = dummy
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        while l1:
            cur.next = l1
            l1 = l1.next
            cur = cur.next
        while l2:
            cur.next = l2
            l2 = l2.next
            cur = cur.next
        return dummy.next

发表于 2022-06-13 16:08:28 回复(0)
Python 3
中正很头像 中正很 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def sortLinkedList(self , head: ListNode) -> ListNode:
        # write code here
        if head is None:
            return head
        tmp = []
        while head:
            tmp.append(head.val)
            head = head.next
        tmp.sort()
        pre = ListNode(-1)
        cur = pre
        while tmp:
            cur.next = ListNode(tmp.pop(0))
            cur = cur.next
        return pre.next

发表于 2022-05-22 12:19:58 回复(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)
C++
满脑子带静电头像 满脑子带静电 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* sortLinkedList(ListNode* head) {
        // write code here
        if(!head || !head->next)
            return head;
        typedef ListNode* list;
        int count = 0;
        list head1 = (list)malloc(sizeof(ListNode));
        list head2 = (list)malloc(sizeof(ListNode));
        list p1 = head1;
        list p2 = nullptr;
        
        head2->next = nullptr;
        list p = head;
        list loc_head2 = nullptr;
        while(p){
            if(count % 2 == 0){
                p1->next = p;
                p1 = p;
                p = p->next;
            }
            else{//头插法获得升序排列的偶数位序列
                loc_head2 = p->next;
                p->next = head2->next;
                head2->next = p;
                p = loc_head2;
            }
            ++count;
        }
        p1->next =nullptr;
        p1 = head1->next;
        p2 = head2->next;
        list before = head1;
        list loc = nullptr;
        while(p1 && p2){
            if(p1->val >= p2->val){
                loc = p2->next;
                p2->next = before->next;
                before->next = p2;
                before = p2;
                p2 = loc;
            }
            else{
                before = p1;
                p1 = p1->next;
            }
        }
        
        if(p2){
            before->next = p2;
        }
        return head1->next;
    }
};

发表于 2022-02-10 22:27:28 回复(0)
C/C++
牛客69143547号头像 牛客69143547号 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* sortLinkedList(ListNode* head) {
        // write code here
        if(head == nullptr || head->next == nullptr)  return head;
        // 先把奇数位链表和偶数位链表拆开
        ListNode* oddCur = head;
        ListNode* evenCur = oddCur->next;
        ListNode* oddHead = oddCur;
        ListNode* evenHead = evenCur;
        while(evenCur != nullptr){
            oddCur->next = evenCur->next;
            if(oddCur->next != nullptr)
                evenCur->next = oddCur->next->next;
            oddCur = oddCur->next;
            evenCur = evenCur->next;
        }
        // 然后把偶数位链表逆序
        evenHead = reverseList(evenHead);
        // 最后把两个升序的链表归并
        return mergeList(oddHead, evenHead);
    }
     
    // 反转链表
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return head;
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while(cur != nullptr){
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
     
    // 合并两个有序链表
    ListNode* mergeList(ListNode* head1, ListNode* head2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while(head1 != nullptr && head2 != nullptr){
            if(head1->val <= head2->val){
                cur->next = head1;
                head1 = head1->next;
            }else{
                cur->next = head2;
                head2 = head2->next;
            }
            cur = cur->next;
        }
        if(head1 != nullptr)  cur->next = head1;
        else  cur->next = head2;
        return dummy->next;
    }
};

发表于 2022-01-10 16:22:01 回复(1)
提交观点

问题信息

链表
难度：
24条回答 4138浏览

热门推荐

通过挑战的用户

查看代码

相关试题

排序奇升偶降链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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