标签：ListNode val int second next 链表 算法 排序 first
1、C
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* sortList(struct ListNode* head){
int n = 0;
struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
newHead->next = head;
struct ListNode *p = head;
while(p!=NULL){
n++;
p = p->next;
}
for(int i=1;i<n;i*=2){
struct ListNode* q = newHead;
for(int j=0;j+i<n;j+=i*2){
struct ListNode* first = q->next;
struct ListNode* second = first;
for(int k=0;k<i;k++){
second = second->next;
}
int a = 0,b = 0;
while(a<i&&b<i&&second){
if(first->val<second->val){
q->next = first;
q = q->next;
first = first->next;
a++;
}
else{
q->next = second;
q = q->next;
second = second->next;
b++;
}
}
while(a<i){
q->next = first;
q = q->next;
first = first->next;
a++;
}
while(b<i&&second){
q->next = second;
q = q->next;
second = second->next;
b++;
}
q->next = second;
}
}
return newHead->next;
}
2、C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode *newHead = new ListNode(-1);
newHead->next = head;
int n = 0;
ListNode* p = head;
while(p!=nullptr){
p = p->next;
n++;
}
for(int i=1;i<n;i*=2){
ListNode* q = newHead;
for(int j=0;j+i<n;j+=i*2){
ListNode *first = q->next;
ListNode *second = first;
for(int k=0;k<i;k++){
second = second->next;
}
int a = 0,b = 0;
while(a<i&&b<i&&second){
if(first->val<second->val){
q->next = first;
q = q->next;
first = first->next;
a++;
}
else{
q->next = second;
q = q->next;
second = second->next;
b++;
}
}
while(a<i){
q->next = first;
q = q->next;
first = first->next;
a++;
}
while(b<i&&second){
q->next = second;
q = q->next;
second = second->next;
b++;
}
q->next = second;
}
}
return newHead->next;
}
};
3、JAVA
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
ListNode newHead = new ListNode(-1,head);
int n = 0;
ListNode p = head;
while(p!=null){
n++;
p = p.next;
}
for(int i=1;i<n;i*=2){
ListNode q = newHead;
for(int j=0;j+i<n;j+=i*2){
ListNode first = q.next;
ListNode second = first;
for(int k=0;k<i;k++){
second = second.next;
}
int a = 0,b = 0;
while(a<i&&b<i&&second!=null){
if(first.val<second.val){
q.next = first;
q = q.next;
first = first.next;
a++;
}
else{
q.next = second;
q = q.next;
second = second.next;
b++;
}
}
while(a<i){
q.next = first;
q = q.next;
first = first.next;
a++;
}
while(b<i&&second!=null){
q.next = second;
q = q.next;
second = second.next;
b++;
}
q.next = second;
}
}
return newHead.next;
}
}
4、Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
newHead = ListNode(-1,head)
n = 0
p = head
while(p is not None):
n += 1
p = p.next
i = 1
while(i<n):
q = newHead
j = 0
while(i+j<n):
first = q.next
second = first
for k in range(i):
second = second.next
a,b = 0,0
while(a<i and b<i and second is not None):
if first.val<second.val:
q.next = first
q = q.next
first = first.next
a += 1
else:
q.next = second
q = q.next
second = second.next
b += 1
while(a<i):
q.next = first
q = q.next
first = first.next
a += 1
while(b<i and second is not None):
q.next = second
q = q.next
second = second.next
b += 1
j += i*2
q.next = second
i *= 2
return newHead.next
标签：ListNode,
val,
int,
second,
next,
链表,
算法,
排序,
first
From： https://www.cnblogs.com/cmkbk/p/17380667.html