合并两个有序链表

一颗蔬菜 2019-09-16 PM 51℃ 0条

某乎的面试题。

原题链接

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return  l1 == null ? l2 : l1;
        }
        
        ListNode head = l1.val > l2.val ? l2 : l1;
        
        ListNode cur1 = head == l1 ? l1 : l2;
        ListNode cur2 = head == l1 ? l2 : l1;
        
        ListNode pre = null; // 最小值指针
        ListNode next = null; // 备份指针
        
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre = cur1; // 指向最小节点
                cur1 = cur1.next; // 移动指针
            } else {
                next = cur2.next;
                
                pre.next = cur2; // 注意pre只是个指针,只是指向最小值
                cur2.next = cur1; // 这两行代码就是将cur2插入到head中
                
                pre = cur2; //  cur2此时已经指向了链表1,因此pre指向的还是链表1
                cur2 = next; // 更新cur2指针,让其重新指向链表2
            }
        }
        // 若cur1为空则l1已经遍历完,直接l2余下的部分追加就好
        pre.next = cur1 == null ? cur2 : cur1; 
        return head; // 返回首指针
    }
}
标签: 算法

非特殊说明,本博所有文章均为博主原创。