Leetcode_14 天算法入门_day10

Posted on | Edited on | In ,
| 3.7k | 31 mins.

今天的主题是递归跟回溯，正好强化一下对递归的理解。

21. Merge Two Sorted Lists

Analysis

这个题放在递归这里怎么感觉不是很合理呢？看到这个题，一般都不会想到用递归来做吧？

Code

method 1

如果不用递归，就只能遍历链表了。按照构造一个新链表的思路，先设置一个头结点，然后分别将 list1 和 list2 中符合条件的结点依次串到头结点后面即可，最后别忘了释放头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* method 1: no recursion */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr) return list2;
        if(list2 == nullptr) return list1;
        if(list1 == nullptr && list2 == nullptr) return nullptr;
        ListNode* head = new ListNode(0);
        ListNode* p = head;
        while(list1 && list2) {
            if(list1->val < list2->val) {
                p->next = list1;
                p = list1;
                list1 = list1->next;
            } else {
                p->next = list2;
                p = list2;
                list2 = list2->next;
            }
        }
        if(list1) p->next = list1;
        if(list2) p->next = list2;
        p = head;
        p = p->next;
        delete(head);
        return p;
    }
};

method 2

为什么会觉得这递归这么难想呢？😂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr) return list2;
        else if(list2 == nullptr) return list1;
        else if(list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

206. Reverse Linked List

Analysis

这个题一看就想用栈来做...
递归是不可能递归的，这辈子都不可能递归的...

Code

method 1

用栈做会稍微麻烦一点，因为要重新构造链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* method 1: use stack */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return nullptr;
        stack<ListNode*> st;
        ListNode* p = head;
        while(p) {
            st.push(p);
            p = p->next;
        }
        ListNode* t = st.top();
        p = t;
        st.pop();
        while(!st.empty()) {
            p->next = st.top();
            st.pop();
            p = p->next;
        }
        p->next = nullptr;
        return t;
    }
};

method 2

不用栈做的话，需要用到 3 个指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* method 2: no stack */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode *pre = nullptr, *cur = head, *next;
        while(cur) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

method 3

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
};

递归真香。注意上面这段代码，newhead 实际上一直都指向原链表的最后一个结点。

method 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode* L = new ListNode(0);
        ListNode *p = L, *t = L;
        while(head) {
            t = head;
            head = head->next;
            t->next = p->next;
            p->next = t;
        }
        p = L;
        p = p->next;
        delete(L);
        return p;
    }
};

实际上，这道题还可以用头插法建立一个新链表，这样建立的链表本身就是逆置的。

Summary

用 2 道链表的题目来巩固递归，感觉不太合理，不过好在能整理一下链表的知识。

Buy me a coffee ? :)
0%