LeetCode 基础题目

分享一些基础题目题解和标答。

#206 [Easy] 反转链表 Reverse Linked List

反转一个单链表。

经典题目，有迭代和递归解法：

迭代解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre, *now, *next, *new_head;
        if(head == NULL || head->next == NULL) return head;
        now = head->next;
        pre = head;
        pre->next = NULL;
        while(true){
            next = now->next;
            now->next = pre;
            if(next != NULL){
                pre = now;
                now = next;
            }
            else
                break;
        }
        return now;
    }
};

迭代解即是用新指针来保存前后元素，遍历一遍链表即可反转。

执行用时 :16 ms, 在所有 C++ 提交中击败了52.36%的用户

内存消耗 :9.1 MB, 在所有 C++ 提交中击败了67.37%的用户

递归解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode *newHead = recur(head, head->next);
        head->next = NULL;
        return newHead;
    }
    
    ListNode* recur(ListNode* node, ListNode* next){
        ListNode *nnext = next->next;
        next->next = node;
        if(nnext == NULL) return next;
        else
            return recur(next, nnext);
    }
};

一个更标准的递归做法基于反向处理链表，可以不需要新的函数。(Java)

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

执行用时 :28 ms, 在所有 C++ 提交中击败了5.93%的用户

内存消耗 :9.3 MB, 在所有 C++ 提交中击败了11.86%的用户

---

#21 [Easy] 合并两个有序链表 Merge Two Sorted Lists

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

标准迭代，递归也可以但是感觉会慢。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *root = new ListNode(0);
        ListNode *iter = root;
        while(l1 != NULL || l2 != NULL){
            if(l1 != NULL && (l2 == NULL || l1->val <= l2->val)){
                iter->next = l1;
                iter = iter->next;
                l1 = l1->next;
            }
            else if(l2 != NULL && (l1 == NULL || l2->val <= l1->val)){
                iter->next = l2;
                iter = iter->next;
                l2 = l2->next;
            }
        }
        return root->next;
    }
    
};

执行用时 :12 ms, 在所有 C++ 提交中击败了83.66%的用户

内存消耗 :8.9 MB, 在所有 C++ 提交中击败了82.84%的用户

---