一聚教程网:一个值得你收藏的教程网站

最新下载

Java利用递归实现链表的归并排序代码示例

时间:2020-09-14 17:11:18 编辑:袖梨 来源:转载

本篇文章小编给大家分享一下Java利用递归实现链表的归并排序代码示例,文章代码介绍的很详细,小编觉得挺不错的,现在分享给大家供大家参考,有需要的小伙伴们可以来看看。

Java利用递归实现链表的归并排序代码示例

利用归并排序,我们可以将时间复杂度降至O(nlogn), 并且我们是对链表进行排序,可以通过修改引用来更改节点顺序,无需像数组一样开辟而外的空间。

利用递归实现链表的归并排序有两个环节:

分割cut环节:

我们可以利用fast,slow快慢双指针实现链表的分割,fast一次移动两位,slow一次移动一位,当fast移动到末尾时,slow移动到中间位置。

利用变量为tmp = slow.next记录后链表的头节点,并将slow.next = null将前后链表断开。

ListNode sortList(ListNode head) {
 if (head == null || head.next == null)
  return head;
 
 ListNode fast = head.next, slow = head;
 while (fast != null && fast.next != null) {
  fast = fast.next.next; // 一次移动两位
  slow = slow.next; // 一次移动一位
 }
 
 ListNode tmp = slow.next; // 记录后链表的头节点
 slow.next = null; // 将前后链表断开
 //...
}

cut递归的终止条件 base case 为当head.next == null,即链表只有一个节点。

归并merge环节:

使用辅助指针,将前后链表后合并为一个有序链表

Java利用递归实现链表的归并排序代码示例

ListNode sortList(ListNode head) {
 //...
 // left 为前链表的头节点, right 为后链表的头节点, 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;
 //...
}

明白上面的两个环节后,就能轻松明白我们完整的算法了。

ListNode sortList(ListNode head) {
    if (head == null || head.next ==null)
      return head;
    // cut过程
    ListNode fast = head.next, slow = head;
    while (fast != null && fast.next != null) {
      fast = fast.next.next;
      slow = slow.next;
    }
    ListNode tmp = slow.next;
    slow.next = null;
	// merage过程
    ListNode left = sortList(head);
    ListNode right = sortList(tmp);
    ListNode h = new ListNode(0);
    ListNode res = 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;

    return res.next;
  }

网站留言

热门栏目