给定一个奇数位升序，偶数位降序的链表，返回对其排序后的链表。
题面解释：例如链表 1->3->2->2->3->1 是奇数位升序偶数位降序的链表，而 1->3->2->2->3->2 则不符合题目要求。
数据范围：链表中元素个数满足 
，链表中的元素大小满足 
[编程题]排序奇升偶降链表
/**
* 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)
直接对链表进行排序的话至少也需要O(nlogn)的时间复杂度，我们注意到链表的奇数位和偶数位其实是有序的，而要将两个有序的部分变为整体有序，归并是再适合不过的了。因此我们可以按照如下的算法来求解：
- 先将链表的拆成奇数位和偶数位两条链表，时间复杂度O(n)；
- 再将偶数位链表进行反转，时间复杂度O(n)；
- 最后归并两个升序的链表，时间复杂度O(n)。
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)
头插法奇偶节点分离
有序链表归并
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)
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)
- 分离奇偶节点
- 翻转偶节点链表
- 合并两个有序链表
这个题在分离奇偶节点时切勿直接在链表上进行操作，通过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)
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)
/**
* 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)
简简单单
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)
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
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)
# 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)
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)
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)
/**
* 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)
class Solution {
public:
ListNode* sortLinkedList(ListNode* head) {
if(!head)return nullptr;
ListNode*pMove=head;
vector<int>tmp;
while(pMove)
{
tmp.push_back(pMove->val);pMove=pMove->next;
}
sort(tmp.begin(),tmp.end());
pMove=head;int j=0;
while(pMove)
{
pMove->val=tmp[j];pMove=pMove->next;j++;
}
return head;
}
};
public:
ListNode* sortLinkedList(ListNode* head) {
if(!head)return nullptr;
ListNode*pMove=head;
vector<int>tmp;
while(pMove)
{
tmp.push_back(pMove->val);pMove=pMove->next;
}
sort(tmp.begin(),tmp.end());
pMove=head;int j=0;
while(pMove)
{
pMove->val=tmp[j];pMove=pMove->next;j++;
}
return head;
}
};
发表于 2022-01-02 13:23:58
回复(0)
// 三步走： 1. 处理奇数段 2. 处理偶数段 3. 合并链表 （面试遇到这题就难搞了，但是至少思路要能说出来）
public class Solution {
public ListNode sortLinkedList (ListNode head) {
if (head.next == null) return head;
// 处理奇数段
ListNode r = head, l1 = new ListNode(0), p1 = l1;
while (r != null && r.next != null) {
p1.next = new ListNode(r.val);
p1 = p1.next;
r = r.next.next;
if (r != null && r.next == null) { // 尾部特殊处理
p1.next = new ListNode(r.val);
p1 = p1.next;
}
}
// 处理偶数段
ListNode q = head.next, l2 = null, node;
while (q != null && q.next != null) {
node = new ListNode(q.val);
node.next = l2;
l2 = node;
q = q.next.next;
if (q != null && q.next == null) { // 尾部特殊处理
node = new ListNode(q.val);
node.next = l2;
l2 = node;
}
}
// 合并处理
ListNode res = new ListNode(0);
node = res;
ListNode b1 = l1.next, b2 = l2;
while (b1 != null && b2 != null) {
if (b1.val < b2.val) {
node.next = new ListNode(b1.val);
b1 = b1.next;
} else {
node.next = new ListNode(b2.val);
b2 = b2.next;
}
node = node.next;
}
if (b1 != null) node.next = b1;
if (b2 != null) node.next = b2;
return res.next;
}
}
发表于 2021-12-30 14:52:57
回复(0)
面试遇到这个，要求只能通过链表操作来完成....... 两个0% 我服了
/**
* 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) {
if (head == nullptr) {
return nullptr;
}
ListNode* pre = head;
ListNode* jHead = new ListNode(0);
ListNode* oHead = new ListNode(0);
//奇数位升序，偶数位降序, 返回升序
ListNode* cur1 = jHead;
int num = 1;
while (pre) {
if (num % 2 != 0) {
ListNode* node = new ListNode(pre->val);
cur1->next = node;
cur1 = cur1->next;
}
else if (num % 2 == 0) {
ListNode* cur2 = oHead;
ListNode* node = new ListNode(pre->val);
if(cur2->next == nullptr){
cur2->next = node;
}
else {
ListNode* next = cur2->next;
cur2->next = node;
node->next = next;
}
}
pre = pre->next;
num++;
}
//两个有序链表合并
ListNode* pre2 = oHead->next;
while (pre2) {
ListNode* pre1 = jHead->next;
ListNode* cur = jHead;
while (pre1) {
if (pre2->val < pre1->val) {
ListNode* node = new ListNode(pre2->val);
cur->next = node;
node->next = pre1;
break;
}
if (pre1->next != nullptr) {
if ((pre2->val > pre1->val) && (pre2->val < pre1->next->val)) {
ListNode* next = pre1->next;
ListNode* node = new ListNode(pre2->val);
pre1->next = node;
node->next = next;
break;
}
}
else {
ListNode* node = new ListNode(pre2->val);
pre1->next = node;
node->next = nullptr;
break;
}
pre1 = pre1->next;
cur = cur->next;
}
pre2 = pre2->next;
}
return jHead->next;
}
};
发表于 2021-12-28 23:47:31
回复(0)
说实话代码逻辑已经非常清晰了，但是就是会运行超时，也不知道哪儿出问题。
head只保留奇节点，tmp只保留偶节点，并记录一个偶节点的头即head->next.
然后反转偶节点组成的链表。
接着tmp作为前驱，每次比较head和evenhead的值，tmp->next永远指向较小的数。
但是就是不知道哪儿有问题。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
ListNode* sortLinkedList(ListNode* head) {
// write code here
if(head==NULL||head->next==NULL) return head;
ListNode *Nhead=(ListNode*)malloc(sizeof(ListNode));
Nhead->next=head;
ListNode *tmp=head->next;//tmp是临时变量
ListNode *evenhead=tmp;//记录偶节点头
while(head->next!=NULL&&tmp->next!=NULL){
head->next=tmp->next;
head=head->next;
tmp->next=head->next;
tmp=tmp->next;
}
//当tmp->next=null时，奇数节点尾部没有指向null
if(tmp->next=NULL) head->next=NULL;
evenhead=reverse(evenhead);//反转所有偶节点
head=Nhead->next;
tmp=Nhead;//此时tmp作为一个前驱
while(head!=NULL&&evenhead!=NULL) {
if(head->val<=evenhead->val) {
tmp->next=head;
head=head->next;
}
else {
tmp->next=evenhead;
evenhead=evenhead->next;
}
tmp=tmp->next;
}
if(head==NULL) tmp->next=evenhead;
else tmp->next=head;
return Nhead->next;
}
ListNode* reverse(ListNode *ehead) {
ListNode *p=NULL;
ListNode *q=NULL;
while(ehead!=NULL) {
p=ehead;
ehead=ehead->next;
p->next=q;
q=p;
}
return p;
}
};
发表于 2021-11-24 14:10:55
回复(2)
问题信息
难度：
20条回答
31收藏
2749浏览
通过挑战的用户
查看代码-
2023-02-19 18:45:07
-
2023-02-19 15:44:42 -
2023-01-05 22:30:20
-
2022-12-03 19:33:46
-
2022-11-02 16:11:48
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
