【hot100-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) {//如果链表为空或者只有一个节点，直接返回链表if (head==null||head.next==null){return head;}//使用快慢指针找到链表的中点ListNode fast=head.next;ListNode slow=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}//链表中间断开，分为左右两部分ListNode tmp=slow.next;slow.next=null;//递归对左右两部分链表进行排序ListNode left=sortList(head);ListNode right=sortList(tmp);//创建一个新节点作为结果链表的起始节点ListNode h=new ListNode(0);ListNode ret=h;//合并已经排序好的链表while(left!=null&&right!=null){if(left.val<right.val){h.next=left;left=left.next;}else{h.next=right;right=right.next;}h=h.next;}//将剩余部分连接到结果链表的末尾h.next=left!=null?left:right;//返回排序后的链表（不包含起始节点h)return ret.next;}
}

ps:

使用快慢指针寻找链表中点这个思路很妙。 

      while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}