《劍指offer》中連結清單相關題目的c++實作

• • LinkedList
  • • • 面試題06 - 從尾到頭列印連結清單（棧；遞歸）
      • 面試題22 - 連結清單中倒數第k個結點（快慢指針）
      • 面試題24-反轉連結清單（三個指針）
      • 面試題25-合并兩個排序的連結清單（歸并排序；遞歸）
      • 面試題35-複雜連結清單的複制（double結點，再拆分）
      • 面試題18-删除連結清單的節點（簡單周遊，修改指針）

LinkedList

面試題06 - 從尾到頭列印連結清單（棧；遞歸）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//----設定棧
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        stack<int>stk; //----設定棧
        while(head){
  
          stk.push(head->val);
            head = head->next;
        }
        vector<int>res; //----放置答案
        while(!stk.empty()){
            res.push_back(stk.top());  //----棧頂元素放入容器
            stk.pop(); //----棧頂元素彈出
        }
        return res;
    }
};
//----遞歸
class Solution {
public:
    vector<int> res;
    vector<int> reversePrint(ListNode* head) {
        if (head != NULL){
            reversePrint(head->next);
            res.push_back(head->val);
        }
    return res;
    }
};
           

面試題22 - 連結清單中倒數第k個結點（快慢指針）

//----快慢指針
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(head==NULL || k==0){
            return NULL;
        }

        ListNode *pFast = head;
        ListNode *pSlow = NULL;

        for(unsigned int i = 0; i<k-1; ++i){
            if(pFast->next != NULL)
                pFast = pFast->next;
            else
                return NULL;
        }

        pSlow = head;
        while (pFast->next != NULL){
            pFast = pFast->next;
            pSlow = pSlow->next;
        }
        
        return pSlow;
    }
};
           

面試題24-反轉連結清單（三個指針）

//----三個指針
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = NULL;
        ListNode *cur = head;

        while (cur) {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};
           

面試題25-合并兩個排序的連結清單（歸并排序；遞歸）

//----歸并排序+dummy指針
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
				if(l1 == NULL)
						return l2;
				else if(l2 == NULL)
						return l1;

        ListNode *dummy = new ListNode(0); //建立一個虛拟的頭結點，用來向後接新的連結清單
        ListNode *cur = dummy;

        while(l1!=NULL && l2!=NULL){
            if(l1->val <= l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = (l1 != NULL)? l1 : l2; 

        return dummy->next;
    }
};
//----遞歸
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        ListNode* result = NULL;
        if(l1->val < l2->val) {
            result = l1;
            result->next = mergeTwoLists(l1->next, l2);
        }
        else {
            result = l2;
            result->next = mergeTwoLists(l1, l2->next);
        }
        return result;
    }
};
           

面試題35-複雜連結清單的複制（double結點，再拆分）

//----double結點，再拆分
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL){
            return NULL;
        }

        //複制結點的val，并放到原結點的後面
        Node* cur = head;
        while(cur){
            Node* curCopy = new Node(cur->val);
            curCopy->next = cur->next;
            
            cur->next = curCopy;
            cur = curCopy->next;
        }

        //構造random
        cur = head;
        while(cur){
            if(cur->random){
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        //拆分連結清單
        cur = head;
        Node* newHead = head->next; //複制連結清單的頭節點
        while(cur->next){
            Node* tmp = cur->next;
            cur->next = tmp->next;
            cur = tmp;
        }
        
        return newHead;
    }
};
           

面試題18-删除連結清單的節點（簡單周遊，修改指針）

//----簡單周遊，修改指針
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
       ListNode* dummy = new ListNode(-1);
       dummy->next = head; 
       ListNode* pre = dummy;
       while(pre->next != NULL){
           if(pre->next->val == val){
               pre->next = pre->next->next;
               break;
           }
           pre = pre->next;
       }
       return dummy->next;
    }
};