03. 回傳鏈表的反序 vector

輸入一個鏈表，按鏈表從尾到頭的順序回傳一個ArrayList，

遞回或者對正序 vector reverse，

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> rst;
        if(head == NULL)return rst;
        rst = printListFromTailToHead(head->next);
        rst.emplace_back(head->val);
        return rst;
    }
};

//----------------------vv---------------------------------
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> rst;
         
        ListNode* pNode = head;
        while(pNode!=NULL){
            rst.emplace_back(pNode->val);
            pNode=pNode->next;
        }
         
        reverse(rst.begin(),rst.end());
        return rst;
    }
};

14. 鏈表中倒數第k個結點+

輸入一個鏈表，輸出該鏈表中倒數第k個結點，

這道題去南大面試還被問了，兩個指標的思路不錯，但是涉及指標的細節很多，容易寫崩，，，

/*
	首先要判斷指標是否為空，以及k是否大于0！！
	然后p1移到最后一個為止，不能指到空
*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead == NULL || k==0)
            return NULL;
         
        ListNode* p1=pListHead;
        ListNode* p2=pListHead;
        
        for(int i=1;i<k;i++){
            if(p1->next==NULL){
                return NULL;
            }
            p1=p1->next;
        }
         
        while(p1->next != NULL){
            p1=p1->next;
            p2=p2->next;
        }
         
        return p2;
    }
};

15. 反轉鏈表

用頭插法新建了一個鏈表，當然不新開鏈表是可以的，似乎正解也是這樣，，然后遞回也可以但沒必要，

16. 合并兩個有序鏈表

輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則，

/*
A:	考歸并操作，
T:	要時刻記得指標所指的結點，不要漏掉！
*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode *newList = new ListNode(0);
        ListNode *p1 = pHead1, *p2 = pHead2, *p3 = newList;
        
        while(p1 && p2){
            if(p1->val <= p2 -> val){
                p3->next = p1;
                p1 = p1->next;
            }else{
                p3->next = p2;
                p2 = p2->next;
            }
            p3 = p3->next;
            p3->next = NULL;
        }
        
        if(p1){
            p3->next = p1;
        }else if(p2){
            p3->next = p2;
        }
        
        return newList->next;
    }
};

25. 復雜鏈表的復制 ++

題目描述

輸入一個復雜鏈表（每個節點中有節點值，以及兩個指標，一個指向下一個節點，另一個特殊指標指向任意一個節點），回傳結果為復制后復雜鏈表的head，（注意，輸出結果中請不要回傳引數中的節點參考，否則判題程式會直接回傳空，

方法 1：map關聯新節點舊結點

方法 2：妙啊（滑稽

public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead==null) return null;
        //1、復制每個結點，如復制結點A得到A1，將結點A1插到結點A后面；
        RandomListNode p=pHead,newHead=new RandomListNode(0),q;
        while(p!=null){
            RandomListNode newNode =new RandomListNode(p.label);
            newNode.next=p.next;
            p.next=newNode;
            p=newNode.next;
        }

        //2、重新遍歷鏈表，復制老結點的隨機指標給新結點，如A1.random = A.random.next;
        p=pHead;
        while(p!=null){
            if(p.random!=null)
                p.next.random=p.random.next;
            p=p.next.next;
        }

        //3、拆分鏈表，將鏈表拆分為原鏈表和復制后的鏈表
        p=pHead;
        q=newHead;
        while(p!=null){
            q.next=p.next;
            p.next=q.next.next;

            p=p.next;
            q=q.next;
        }

        return newHead.next;
    }
}

36. 兩個鏈表的第一個公共結點+

從第一個公共結點開始，都為公共結點，

方法 1：借助輔助堆疊，

我們可以把兩個鏈表的結點依次壓入到兩個輔助堆疊中，這樣兩個鏈表的尾結點就位于兩個堆疊的堆疊頂，接下來比較兩個堆疊頂的結點是否相同，如果相同，則把堆疊頂彈出繼續比較下一個，直到找到最后一個相同的結點，此方法也很直觀，時間復雜度為O(m+n)，但使用了O(m+n)的空間，相當于用空間換區了時間效率的提升，

方法 2：將兩個鏈表設定成一樣長，

具體做法是先求出兩個鏈表各自的長度，然后將長的鏈表的頭砍掉，也就是長的鏈表先走幾步，使得剩余的長度與短鏈表一樣長，這樣同時向前遍歷便可以得到公共結點，時間復雜度為O(m+n)，不需要額外空間，

方法 3：將兩個鏈表拼接起來，

將兩個鏈表進行拼接，一個鏈表1在前鏈表2在后，另一個鏈表2在前鏈表1在后，則合成的兩個鏈表一樣長，然后同時遍歷兩個鏈表，就可以找到公共結點，時間復雜度同樣為O(m+n)，

//方法3
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
        ListNode *p1 = pHead1;
        ListNode *p2 = pHead2;
        while(p1!=p2){
            p1 = (p1==NULL ? pHead2 : p1->next);
            p2 = (p2==NULL ? pHead1 : p2->next);
        }
        return p1;
    }
};

55. 鏈表中環的入口結點+++

題目描述：

給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出null，

方法 1：斷鏈法

采用斷鏈法,訪問過的節點都斷開，最后到達的那個節點一定是回圈的入口節點，

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        ListNode fast = pHead.next;
        ListNode slow = pHead;
        while (fast != null) {
            slow.next = null;
            slow = fast;
            fast = fast.next;
        }
        return slow;
    }
}

方法 2：快慢指標

利用快慢指標，快指標一次走兩步，慢指標一次走一步，具體思路如下：
①判斷是否有環：若鏈表中存在環，快慢指標一定會在環上某一點相遇（因為相對速度為1）；
②確定環的起點：
? 設x為環前面的路程（黑色路程），a為環入口到相遇點的路程（藍色路程，假設順時針走）， c為環的長度（藍色+橙色路程），則有

• 慢指標走的路程 Sslow = x + m * c + a，
• 快指標走的路程為Sfast = x + n * c + a，
• 且2 Sslow = Sfast

? 可得 x = c - a，即相遇點后環剩余部分的路程，所以，我們可以讓一個指標從鏈表起點開始走，讓一個指標從相遇點開始繼續往后走，倆指標會在環的起點相遇，

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead==null || pHead.next == null ||pHead.next.next ==null)
            return null;

        // 判環
        ListNode fast= pHead.next.next;
        ListNode slow= pHead.next;

        while (fast!=slow){
            if(fast.next!=null && fast.next.next!=null){
                fast = fast.next.next;
                slow = slow.next;
            } else{
                return null;
            }
        }

        //回圈出來的話就是有環，且此時fast==slow，快慢指標在相遇點
        fast=pHead;
        while (fast!=slow){//將在環的起點相遇
            fast=fast.next;
            slow=slow.next;
        }

        return slow;
    }
}

56. 洗掉鏈表中重復的結點+

題目描述：

在一個排序的鏈表中，存在連續重復的結點，請洗掉該鏈表中重復的結點，重復的結點不保留，回傳鏈表頭指標，
例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5

很容易寫錯了，

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode newHead = new ListNode(-10000000);//增加頭節點統一操作
        newHead.next=pHead;

        ListNode pre = newHead, cur;

        while(pre!=null && pre.next!=null && pre.next.next!=null){
            if(pre.next.val==pre.next.next.val){//pre指向重復元素的前一個元素
                cur=pre.next;
                while(cur.next!=null&&cur.next.val==pre.next.val){
                    cur=cur.next;
                }
                pre.next=cur.next;
            }
            else{// 放在else里是因為剛刪完元素后，不能保證pre指標后面兩個元素不等，所以pre要保持不動
                pre = pre.next;
            }
        }

        return newHead.next;
    }
}

標籤：其他

上一篇：容斥法解決錯排問題

下一篇：資料結構之——八大排序演算法