https://leetcode.cn/problems/sort-list/description/https://leetcode.cn/problems/sort-list/description/
解题思路:
归并排序,先拿到链表长度,每次遍历到一半,进行分割,后序双指针合并。
/** * 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 { ListNode gb(ListNode head, int len){ if(len<=1){ return head; } ListNode m_node=head; for(int i=1;i<len/2;i++){ m_node=m_node.next; } ListNode t=m_node; m_node=m_node.next; t.next=null; ListNode now=new ListNode(),ans=now; ListNode l=gb(head,len/2); ListNode r=gb(m_node,len-len/2); int llen=len/2,rlen=len-len/2; while(llen!=0||rlen!=0){ if(llen==0||(rlen>0&&l.val>=r.val)){ ans.next=r; r=r.next; ans=ans.next; rlen-=1; } else{ ans.next=l; l=l.next; ans=ans.next; llen-=1; } } return now.next; } public ListNode sortList(ListNode head) { int len=0; ListNode temp=head; while(temp!=null){ temp=temp.next; len+=1; } return gb(head,len); } }