归并链表

题目出处

• Leetcode 21. 合并两个有序链表
• 剑指 Offer - 25 - 合并两个排序的链表
• 面试实际遇到过

合并两个有序的链表

1 题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

2 解题思路

2.1 递归

class Solution{
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

2.2 迭代

class Solution{
    public ListNode mergeTwoLists(ListNode head1, ListNode head2){
        
        ListNode tempHead = new ListNode(-1);
        ListNode resultHead = tempHead;
        
        while (head1 != null && head2 != null ){
            if (head1.val <= head2.val){
                tempHead.next = head1;
                head1 = head1.next;
            }else {
                tempHead.next = head2;
                head2 = head2.next;
            }
            tempHead = tempHead.next;
        }
        
        if(head1 != null){
            tempHead.next = head1;
        }
        if(head2 != null){
            tempHead.next = head2;
        }
        
        return resultHead.next;
    }
}

单链表的归并排序

1 题目描述

2 解题思路

2.2 迭代

class Solution{
    //单链表的归并排序
    public ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 快慢指针，得到链表中间的数
        ListNode slow = head;
        // fast 从第二个结点起，避免只有两个节点的时候，无法分治
        ListNode fast = head.next;
        while ( f.next !=null && f.next.next !=null ){
            slow = slow.next;
            fast = fast.next.next;
        }
        //拆分链表
        ListNode middle = slow.next;
        slow.next = null;
        //递归调用上面那个 归并两个有序的链表 方法
        return mergeTwoLists(mergeSort(head), mergeSort(middle));
    }
}