刷题《剑指Offer》day09

题目来源：力扣《剑指Offer》第二版
完成时间：2022/07/31

22. 链表中倒数第k个节点

我的题解

这题比较简单，用栈实现即可。另外还有快慢指针的解法，空间复杂度O(1)，比用栈实现更好，这里就不写了。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    
        stack<ListNode*> s1;
        ListNode* tmp = head;
        while(tmp != nullptr) {
    
            s1.push(tmp);
            tmp = tmp->next;
        }
        int count = 1;
        while(count < k) {
    
            s1.pop();
            count++;
        }
        return s1.top();
    }
};

24. 反转链表

我的题解

这题要用三指针，tmp指针用来遍历整个链表，cur和pre用来实现相邻两个节点的反转。

/** * 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* cur = head;
        ListNode* pre = nullptr;
        ListNode* tmp = nullptr;
        while(cur != nullptr){
    
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

递归写法

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
    
        if(cur == NULL) return pre;
        ListNode* tmp = cur->next;
        cur->next = pre;
        return reverse(cur,tmp);
    }

    ListNode* reverseList(ListNode* head) {
    
        return reverse(NULL,head);
    }
};

其他题解

这种递归的方式更简洁，但是要注意需要多定义一个tmp指针用来接收反转之后的头指针。

/** * 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 == nullptr || head->next == nullptr) {
    
            return head;
        }
        ListNode* tmp = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tmp;
    }
};

25. 合并两个排序的链表

我的题解

这题也比较简单，直接上代码

/** * 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* head = new ListNode(-1);
        ListNode* pre = head;
        while(l1 != NULL && l2 != NULL){
    
            if(l1->val > l2->val){
    
                pre->next = l2;
                l2 = l2->next;
            }else {
    
                pre->next = l1;
                l1 = l1->next;
            }
            pre = pre->next;
        }
        if(l1 == NULL) pre->next = l2;
        else pre->next = l1;
        return head->next;
    }
};