鏈表概念:

• 是由一組節(jié)點組成的的集合，其中每個數(shù)據(jù)項都是一個節(jié)點的一部分，每個節(jié)點還包含指向下一個節(jié)點的鏈接。
• 鏈表是結(jié)構(gòu)體最重要的應用， 它是一種非固定長度的數(shù)據(jù)結(jié)構(gòu)，是一種動態(tài)存儲技術， 它能夠根據(jù)數(shù)據(jù)的結(jié)構(gòu)特點和數(shù)量使用內(nèi)存，尤其適用于數(shù)據(jù)個數(shù)可變的數(shù)據(jù)存儲。

鏈表基本元素

• 1.節(jié)點：每個節(jié)點有兩個部分，左邊部分稱為值域，用來存放用戶數(shù)據(jù)；右邊部分稱為指針域，用來存放指向下一個元素的指針。
• 2.head:head節(jié)點永遠指向第一個節(jié)點
• 3.tail: tail永遠指向最后一個節(jié)點

• 4.None:鏈表中最后一個節(jié)點的指針域為None值

  
  
  image.png

頭指針與頭結(jié)點以及首元結(jié)點的關系:

image.png

題目

將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。

示例

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

思路一: 迭代

• 創(chuàng)建一個新的鏈表用來存儲排列數(shù)據(jù), 然后用while循環(huán)檢測 l1和 l2中的val值,如果l1.var<=l2.var,那么就讓新鏈表的next指針指向l1的val,,然后改變l1的指針指向并且將l1的下一個值指向l1,依次迭代,反之,如果l1.val>l2.var 那么就讓新鏈表的next指針指向l2的val,,然后改變l2的指針指向并且將l2的下一個值指向l2,依次迭代,直到左右節(jié)點迭代完,判斷l(xiāng)1是否為空,返回新鏈表l3.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        // 頭結(jié)點
        ListNode head;
        if (l1.val <= l2.val) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur = cur.next = l1;
                l1 = l1.next;
            } else {
                cur = cur.next = l2;
                l2 = l2.next;
            }
        }
        
        if (l1 == null) {
            cur.next = l2;
        } else if (l2 == null) {
            cur.next = l1;
        }
        return head;
        
    }
}

思路二 遞歸

public ListNode mergeTwoLists(ListNode k1, ListNode k2) {
        if (k1 == null) return k2;
        if (k2 == null) return k1;
        
        if (k1.val <= k2.val) {
            k1.next = mergeTwoLists(k1.next, k2);
            return k1;
        } else {
            k2.next = mergeTwoLists(k1, k2.next);
            return k2;
        }
    }