一 題目詳解

https://leetcode-cn.com/problems/merge-two-sorted-lists/

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

實例：

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

image.png

二 思路分析

思路一 迭代

image.png

思路二 遞歸

• 第一次遞歸

image.png

• 第二次遞歸

image.png

• 第三次遞歸

image.png

• 第四次遞歸

image.png

• 第五次遞歸

image.png

三 代碼實現(xiàn)

3.1 迭代實現(xiàn)

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    
    // 構造兩個鏈表
    LinkNode *k3 = [[LinkNode alloc] initWithElement:@(5) next:nil];
    LinkNode *k2 = [[LinkNode alloc] initWithElement:@(3) next:k3];
    LinkNode *k1 = [[LinkNode alloc] initWithElement:@(1) next:k2];
    
    LinkNode *k5 = [[LinkNode alloc] initWithElement:@(4) next:nil];
    LinkNode *k4 = [[LinkNode alloc] initWithElement:@(2) next:k5];
    
    // 方法一
    LinkNode *k = [self mergeTwoLists2:k1 k2:k4];
    while (k) {
        NSLog(@"%@",[k description]);
        k = k.next;
    }
}

/// 方法一:合并2個有序鏈表
- (LinkNode *)mergeTwoLists2:(LinkNode *)k1 k2:(LinkNode *)k2 {
    if (k1 == nil) return k2;
    if (k2 == nil) return k1;
    
    // 虛擬頭結點(dummy head)
    LinkNode *head = [[LinkNode alloc] init];
    LinkNode *cur = head;
    
    while (k1 != nil && k2 != nil) {
        if (k1.value <= k2.value) {
            cur = cur.next = k1;
            k1 = k1.next;
        } else {
            cur = cur.next = k2;
            k2 = k2.next;
        }
    }
    
    if (k1 == nil) {
        cur.next = k2;
    } else if (k2 == nil) {
        cur.next = k1;
    }
    
    return head.next;
}

• 運行結果

2019-11-11 23:20:13.400891+0800 02_MergeTwoLists[25866:963864] null_1_2
2019-11-11 23:20:13.401120+0800 02_MergeTwoLists[25866:963864] null_2_3
2019-11-11 23:20:13.401257+0800 02_MergeTwoLists[25866:963864] null_3_4
2019-11-11 23:20:13.401382+0800 02_MergeTwoLists[25866:963864] null_4_5
2019-11-11 23:20:13.401481+0800 02_MergeTwoLists[25866:963864] null_5_null

3.2 遞歸實現(xiàn)

/// 方法一:遞歸
/// 1.只要是用到遞歸,首先要搞清楚一個問題,這個遞歸函數(shù)的功能是什么
/// 2.遞歸基:邊界
- (LinkNode *)mergeTwoLists:(LinkNode *)k1 k2:(LinkNode *)k2 {
    if (k1 == nil) return k2;
    if (k2 == nil) return k1;
    
    if (k1.value <= k2.value) {
        k1.next = [self mergeTwoLists:k1.next k2:k2];
        return k1;
    } else {
        k2.next = [self mergeTwoLists:k1 k2:k2.next];
        return k2;
    }
}

• 運行結果

2019-11-11 23:26:42.654185+0800 02_MergeTwoLists[26034:968649] null_1_2
2019-11-11 23:26:42.654375+0800 02_MergeTwoLists[26034:968649] null_2_3
2019-11-11 23:26:42.654482+0800 02_MergeTwoLists[26034:968649] null_3_4
2019-11-11 23:26:42.654593+0800 02_MergeTwoLists[26034:968649] null_4_5
2019-11-11 23:26:42.654691+0800 02_MergeTwoLists[26034:968649] null_5_null

本文參考MJ老師的每周一道算法題，非常感謝MJ老師

項目鏈接地址- 02_MergeTwoLists

每周一道算法題 - 筆記