劍指Offer 25. 合并兩個排序的連結清單

劍指Offer 25. 合并兩個排序的連結清單

這題是一道簡單題，如果學習了資料結構當中的連結清單的話，可以很輕松就想出解題過程：

/**
 * 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) {
        ListNode newhead=new ListNode(1);
        ListNode temNode = newhead;
        ListNode temNode1 = l1;
        ListNode temNode2 = l2;
        while (temNode1!=null && temNode2!=null) {
            if (temNode1.val<=temNode2.val) {
                temNode.next=new ListNode(temNode1.val);
                temNode1=temNode1.next;
            }
            else {
                temNode.next=new ListNode(temNode2.val);
                temNode2=temNode2.next;
            }
            temNode = temNode.next;
        }
        if (temNode1!=null || temNode2!=null) {
            ListNode newNode = temNode1==null ? temNode2:temNode1;
            while (newNode!=null) {
                temNode.next = new ListNode(newNode.val);
                newNode = newNode.next;
                temNode = temNode.next;
            }
        }
        return newhead.next;
    }
}
           

先建立兩個節點newhead和temnode作為我們要傳回連結清單的頭節點和替身，再建立兩個節點temNode1和temNode2來代替l1和l2。當temNode1和temNode2都不為null時，也就是兩個連結清單都沒有周遊完，然後根據temNode1和temNode2的值來決定将誰的值作為新加在temNode後的節點的值。當temNode1或temNode2中有一個為null，即短的那一個連結清單周遊完了，我們需要周遊較長的連結清單的剩餘部分。

寫完後，經過簡單的調試，送出通過。

看了看代碼，發現代碼中還有待改善的地方：

• 可以不使用temNode1和temNode2來代替l1和l12
• temNode.next等于的是根據值建立的節點，有一點麻煩

根據上面的想法後用Python3寫的代碼：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        newhead = ListNode()
        head = newhead
        while l1!=None and l2!=None:
            if l1.val<=l2.val:
                newhead.next = l1
                l1 = l1.next
            else:
                newhead.next = l2
                l2 = l2.next
            newhead = newhead.next
        if l1!=None or l2!=None:
            newNode = l2 if l1 == None else l1
            while newNode != None:
                newhead.next = newNode
                newhead = newhead.next
                newNode = newNode.next

        return head.next