[Leetcode]148. 排序链表(归并排序)

题目

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3

输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0

输出: -1->0->3->4->5

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/sort-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

归并排序的递归实现。

在递归过程中：

- 若只有一个节点，直接返回

- 找到中点，分成左右两个链表

- 递归左边链表

- 递归右边链表

- 两路归并排序

- 返回排好序的链表

待做

归并排序的非递归实现

代码

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

class Solution {

   public ListNode sortList(ListNode head) {

		return head == null ? null : merge(head);

	}

	private ListNode merge(ListNode head) {// 归并排序

		// 如果只剩一个节点，直接返回节点

		if (head == null || head.next == null) {//

			return head;

		}

		// 找到链表中点

		ListNode pSlow = head;

		ListNode pFast = head;

		ListNode pPre = null;

		while (pFast != null && pFast.next != null) {

			pPre = pSlow;

			pFast = pFast.next.next;

			pSlow = pSlow.next;

		}

		pPre.next = null;// 把中点与中点前的节点切断；

		ListNode lList = merge(head);// 返回已排好序的左半边链表

		ListNode rList = merge(pSlow);// 返回已排好序的右半边链表 //

		ListNode sortList = mergeSort(lList, rList);// 对head的链表归并排序 //

		return sortList;

	}

	private ListNode mergeSort(ListNode l, ListNode r) {// 两路归并

		ListNode dummyHead = new ListNode(-1);

		ListNode cur = dummyHead;

		while (l != null && r != null) {

			if (l.val <= r.val) {

				cur.next = l;

				l = l.next;

				cur = cur.next;

			} else {

				cur.next = r;

				r = r.next;

				cur = cur.next;

			}

		}

		if (l != null) {

			cur.next = l;

		}

		if (r != null) {

			cur.next = r;

		}

		return dummyHead.next;

	}

}

巴特西

[Leetcode]148. 排序链表(归并排序)

题目

题解

待做

代码

最新文章

热门文章