* Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };

考察鏈表的題目不會要求我們時間復(fù)雜度，因為鏈表并不像是數(shù)組那樣，可以方便的使用各種排序算法和查找算法。
因為鏈表涉及到大量的指針操作，所以鏈表的題目考察的主要是兩個方面：代碼的魯棒性和簡潔性。
不要一開始想到思路就開始寫代碼，最好是先想好測試用例，然后再讓自己的代碼通過所有的測試用例。
創(chuàng)建節(jié)點：ListNode* node= new ListNode();
刪除刪除節(jié)點：delete node; node = nullptr

【面試題05：從尾到頭打印鏈表】

題目：輸入個鏈表的頭結(jié)點，從尾到頭反過來打印出每個結(jié)點的值。
思路： 1、棧。入棧節(jié)點；出棧打印。 2、遞歸。

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        stack<ListNode*> nodes;
        ListNode* pNode = head;
        vector<int> a;
        while(pNode != nullptr){
            nodes.push(pNode);
            pNode = pNode->next;
        }
        while(!nodes.empty()){
            pNode = nodes.top();
            a.push_back(pNode->val);
            nodes.pop();
        }
        return a;
    }
};

【面試題13：在O(1)時間刪除鏈表結(jié)點】

題目：給定單向鏈表的頭指針和一個節(jié)點指針，定義一個函數(shù)在O(1)時間刪除該節(jié)點。

分類：
1、如果要刪除的結(jié)點位于鏈表的尾部，那么它就沒有下一個結(jié)點，這時我們就必須從鏈表的頭結(jié)點開始，順序遍歷得到該結(jié)點的前序結(jié)點，并完成刪除操作。pNode->next = nullptr; delete pToBeDeleted; pToBeDeleted = nullptr;
2、如果鏈表中只有一個結(jié)點，而我們又要刪除鏈表的頭結(jié)點，也就是尾結(jié)點，delete pToBeDeleted; pToBeDeleted = nullptr; *pHead=nullptr。
3、一般情況，記錄下一節(jié)點，復(fù)制到該節(jié)點，并刪除下一節(jié)點。

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
    if (!pListHead || !pToBeDeleted)
        return;
    if (pToBeDeleted->m_pNext != NULL)
    {
        ListNode* pNext = pToBeDeleted->m_pNext;
        pToBeDeleted->m_nValue = pNext->m_nValue;
        pToBeDeleted->m_pNext = pNext->m_pNext;
        delete pNext;
        pNext = NULL;
    }
    //鏈表只有一個結(jié)點，刪除頭結(jié)點（也是尾結(jié)點）
    else if(*pListHead == pToBeDeleted)
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;
        *pListHead = NULL;
    }
    //要刪除的結(jié)點是尾結(jié)點
    else{
        ListNode* pNode = *pListHead;
        while (pNode->m_pNext != pToBeDeleted) 
            pNode = pNode->m_pNext;

        pNode->m_pNext = NULL;
        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

【面試題15：鏈表中倒數(shù)第k個結(jié)點】 Remove Nth Node From End of List

分三種情況：
1、空鏈表以及n=0，無效返回nullptr;
2、計算節(jié)點間隔，定義快節(jié)點（并判斷n值是否有效），然后通過遍歷快慢節(jié)點，確定待刪節(jié)點
1、待刪節(jié)點為頭結(jié)點；
2、非頭節(jié)點；ps：刪除節(jié)點

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head ==nullptr || n == 0)
            return nullptr;
        ListNode* p1 = head;
        ListNode* p2 = head;  
        ListNode* p2Pre = nullptr;
        for (int i = 0;i<n;i++){
            if (p1 == nullptr)
                return nullptr;
            else
                p1 = p1->next; 
        }//提前走n步，并判斷n值是否在有效區(qū)間內(nèi)
        while(p1 != nullptr){
            p1 = p1->next; 
            p2Pre = p2;
            p2 = p2->next;
        }//同步遍歷，并記錄刪除節(jié)點的上一節(jié)點
        if(p2Pre == nullptr){
            head = p2->next;
        }
        else{
            p2Pre->next = p2->next;
        }//判斷刪除節(jié)點是否為首節(jié)點 
        free(p2);//刪除節(jié)點；
        return head;
       
    }
};

鏈表有環(huán)問題：是否有環(huán)Linked List Cycle，環(huán)入口節(jié)點

用兩個指針去遍歷，一個指針一次走兩步，一個指針一次走一步，如果有環(huán)，兩個指針肯定會在環(huán)中相遇。相遇點即為環(huán)內(nèi)某個節(jié)點。時間復(fù)雜度為O（n）。
環(huán)入口兩種思路：
1、采用兩個指針，一快一慢相隔環(huán)長度節(jié)點，相遇即為入口節(jié)點。環(huán)長度根據(jù)上面判斷是否有環(huán)的相遇點計算，相遇點出發(fā)到在此回到該節(jié)點時計數(shù)。
2、在上面的相遇節(jié)點處斷開（當(dāng)然函數(shù)結(jié)束時不能破壞原鏈表），這樣就形成了兩個相交的單鏈表，求進入環(huán)中的第一個節(jié)點也就轉(zhuǎn)換成了求兩個單鏈表相交的第一個節(jié)點。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* pfast = head;
        ListNode* pslow = head;
        while(pfast != nullptr){
            pfast = pfast->next;
            if(pfast == pslow)
                return true;
            pslow = pslow->next; 
            if(pfast != nullptr)
                pfast = pfast->next;
        }
        if(pfast == nullptr)
            return false; 
    }
};
class Solution {
public:
    /*1） 確定有無環(huán)
    #2） 確定環(huán)節(jié)點數(shù)
    #3） 確定環(huán)入口節(jié)點*/
    ListNode* MeetingNode(ListNode* pHead)
    {
        if (pHead == nullptr)
            return nullptr;
        ListNode* pSlow = pHead;
        if (pSlow->next == nullptr)
            return nullptr;
        ListNode* pFast = pSlow->next;
        while(pFast!= nullptr){
            if (pFast == pSlow)
                return pFast;
            pSlow = pSlow->next;
            pFast = pFast->next;
            if (pFast != nullptr)
                pFast = pFast->next;
        }
        return nullptr;
    }
    
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode* meetingNode = MeetingNode(pHead);
        if (meetingNode == nullptr)
            return nullptr;
        int count = 1;
        ListNode* pNode = meetingNode;
        while(pNode->next != meetingNode){
            pNode = pNode->next;
            count++;
        }
        pNode = pHead;
        for (int i=0; i<count; i++)
            pNode = pNode->next;
        ListNode* pNode1 = pHead;
        while(pNode != pNode1){
            pNode = pNode->next;
            pNode1= pNode1->next;
        }
        return pNode;
    }
};

【面試題16：反轉(zhuǎn)鏈表】

題目：定義一個函數(shù)，輸入一個鏈表的頭結(jié)點，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭結(jié)點。

需記錄三個節(jié)點?？梢圆捎幂o助結(jié)點，避免考慮頭結(jié)點情況。一般需要考慮當(dāng)前節(jié)點的上一結(jié)點時可采用輔助頭結(jié)點。

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) { 
        ListNode* pNode = pHead; 
        ListNode* preNode = nullptr;
        ListNode* nextNode = nullptr; 
        while(pNode != nullptr){
            nextNode = pNode->next;
            pNode->next = preNode;
            
            preNode = pNode;
            pNode = nextNode;
        }
        return preNode;
    }
};

【面試題17：合并兩個排序的鏈表】Merge Two Sorted Lists

題目：輸入兩個遞增排序的鏈表，合并這兩個鏈表并使新鏈表中的結(jié)點仍然是按照遞增排序的

每次取兩個鏈表的頭結(jié)點進行比較；剩下的兩個鏈表仍是排序鏈表，屬于遞歸問題。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr)
            return l2;
        else if(l2 == nullptr)
            return l1;
        ListNode* MergeHead = nullptr;
        if(l1->val>l2->val){
            MergeHead = l2;
            MergeHead->next = mergeTwoLists(l1,l2->next);
        }
        else{
            MergeHead = l1;
            MergeHead->next = mergeTwoLists(l1->next,l2);
        }
        return MergeHead;
    }
};

【面試題26：復(fù)雜鏈表的復(fù)制】

題目：請實現(xiàn)函數(shù)ComplexListNode clone(ComplexListNode head),復(fù)制一個復(fù)雜鏈表。在復(fù)雜鏈表中，每個結(jié)點除了有一個next 域指向下一個結(jié)點外，還有一個sibling 指向鏈表中的任意結(jié)點或者null。

1、兩步：第一步復(fù)制順序節(jié)點，第二部復(fù)制隨機節(jié)點，節(jié)點的定位需要O(n)。總的時間復(fù)雜度O(nn)。
2、三步：順序節(jié)點的復(fù)制，并順序連接在該節(jié)點的后面；隨機節(jié)點的復(fù)制根據(jù)原節(jié)點的定位；奇偶拆分鏈表。時間復(fù)雜度O(n).
ps：完成第一步的順序節(jié)點復(fù)制，才能定位之后的隨機節(jié)點；生成節(jié)點: ListNode* Node= new ListNode(0);

struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        CloneSequenceNode(pHead);
        CloneRandomNode(pHead); 
         
        return SeparateList(pHead);
    }
    void CloneSequenceNode(RandomListNode* pHead){
        RandomListNode* pNode = pHead;
        while(pNode != nullptr){
            RandomListNode* cloneNode = new RandomListNode(pNode->label); 
            cloneNode->next = pNode->next;
            //cloneNode->random = nullptr;
            pNode->next = cloneNode;
            pNode = cloneNode->next;
        }
    }
    void CloneRandomNode(RandomListNode* pHead){
        RandomListNode* pNode = pHead;
        while(pNode != nullptr){
            RandomListNode* cloneNode = pNode->next;
            if (pNode->random != nullptr){
                cloneNode->random = pNode->random->next;
            }
            pNode = cloneNode->next;
        }
    }
    RandomListNode* SeparateList(RandomListNode* pHead){
        RandomListNode* pNode = pHead;
        RandomListNode* cloneHead = nullptr;
        RandomListNode* clonepNode= nullptr;
        if (pNode != nullptr){
            cloneHead = pNode->next;
            clonepNode = cloneHead;
        }
        while(pNode !=nullptr ){
            pNode->next = clonepNode->next;
            pNode = pNode->next; 
            if (pNode != nullptr){
                clonepNode->next = pNode->next;
                clonepNode = clonepNode->next;  
            } 
        }
        return cloneHead;
    }
};

查找單鏈表的中間結(jié)點

典型的兩個指針問題。定義兩個指針，快指針一次走兩步，慢指針一次走一步?？熘羔樧叩阶詈笠粋€節(jié)點，慢指針對應(yīng)的就是中間節(jié)點

【面試題37：兩個鏈表的第一個公共結(jié)點】 intersection-of-two-linked-lists

題目：輸入兩個鏈表，找出它們的第一個公共結(jié)點。

第一個問題：是否相交。如果相交兩個鏈表的尾節(jié)點一定相同。
第二個問題：第一個相交公共點。
1、異步遍歷找相同節(jié)點。時間復(fù)雜度O(mn)
2、第一公共節(jié)點后兩鏈表重合，從后往前遍歷。采用后進先出（棧）。棧的定義：std::stack<ListNode*>nodes。時間復(fù)雜度O(m+n)，空間復(fù)雜度O(m+n)
3、先計算兩鏈表長度差，讓長鏈表先走差步，然后同步遍歷兩鏈表找到第一個相同節(jié)點。時間復(fù)雜度O(m+n)

class Solution {
public: 
    ListNode*getIntersectionNode( ListNode* pHead1, ListNode* pHead2) {
        int Listlength1 = GetLength(pHead1);
        int Listlength2 = GetLength(pHead2);
        
        int Listlengthdiff =  Listlength1- Listlength2;
        ListNode* Listlong = pHead1;
        ListNode* Listshort = pHead2;
        if(Listlength2>Listlength1){
            Listlong = pHead2;
            Listshort = pHead1;
            Listlengthdiff = Listlength2 - Listlength1;
        }
        for (int i =0; i<Listlengthdiff;i++)
            Listlong = Listlong->next;
        while((Listlong != nullptr) && (Listshort != nullptr) && (Listlong !=Listshort)){
            Listlong = Listlong->next;
            Listshort = Listshort->next;
        }
        ListNode* ListCommonNode= Listshort;
        return ListCommonNode; 
    }
    int GetLength(ListNode* pHead){
        int length = 0;
        ListNode* pNode = pHead;
        while(pNode != nullptr){
            pNode = pNode->next;
            length = length+1;
        }
        return length;
    }
};

Add Two Numbers

題目：Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0 -> 8Explanation: 342 + 465 = 807.
思路：逐節(jié)點相加。注意點：1）進位問題，2）鏈表長短不一，3）兩鏈表遍歷完后可能仍有進位，還需循環(huán)一次。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* pHead = nullptr;
        ListNode* pNode = pHead;
        ListNode* pNode1 = l1;
        ListNode* pNode2 = l2;
        int dedigit = 0; 
        while(pNode1 != nullptr || pNode2!=nullptr || dedigit){
            int pNode1val = pNode1 ? pNode1->val : 0;
            int pNode2val = pNode2 ? pNode2->val : 0;
            ListNode* node = new ListNode((pNode1val+pNode2val+ dedigit)%10 );
            dedigit = (pNode1val+pNode2val+ dedigit)/10;
            if(pHead == nullptr){
                pHead = node;
                ListNode* pNode = pHead;
            } 
            else 
                pNode->next = node;
            pNode = node;
            pNode1 = pNode1 ? pNode1->next : pNode1;
            pNode2 = pNode2 ? pNode2->next : pNode2;
        } 
        return pHead; 
    }
    unsigned int ListReverseDigit(ListNode* pHead){ 
        ListNode* pNode = pHead;
        unsigned int digit = 0;
        int count = 1;
        while(pNode!=nullptr){
            digit = digit+count*pNode->val;
            count = count*10;
            pNode = pNode->next;
        }
        return digit; 
    }//neglect value range of int;;
    ListNode* DigitReverseList(unsigned int digit){  
        ListNode* pHead= nullptr;
        ListNode* pNode= pHead;
        int dedigit = 1;
        int redigit = 0; 
        while(dedigit !=0 ){
            dedigit = digit/10;
            redigit = digit%10;
            digit = dedigit; 
            ListNode* node = new ListNode(redigit);
            if(pHead == nullptr)
                pHead = node;
            else
                pNode->next = node;
            pNode = node;
        } 
        return pHead;
    }
};

Remove Duplicates from Sorted List II

題目：刪除鏈表中重復(fù)的節(jié)點。
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5

1）第一個節(jié)點就為待刪除節(jié)點；
2）中間節(jié)點待刪除；
3）尾節(jié)點待刪除
ps:增加一個頭節(jié)點，不許考慮第一個節(jié)點待刪除的情況。

// 三種情況：1）空；2）1-1-1，2）1-1-2, 3)1-2-2-3, 4)1-2-2     1-1-2-2-3-4-4
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr)
            return nullptr;
        /*ListNode* preNode = nullptr;
        ListNode* pNode = head;
        while(pNode!= nullptr){
            //判斷是否有相同節(jié)點
            if (pNode->next != nullptr && (pNode->val == pNode->next->val)){
                int val = pNode->val;
                while(pNode != nullptr && (pNode->val == val))
                        pNode = pNode->next;//找到下一個不同節(jié)點
                if(preNode == nullptr)//如果重復(fù)節(jié)點被頭指針指向
                    head = pNode;
                else
                    preNode->next = pNode;
            }
            else{
                preNode = pNode;
                pNode = pNode->next;
            }
        }
        return head; 
    }*/
        ListNode* prehead = new ListNode(0);
        prehead->next = head;
        ListNode* preNode = prehead;
        ListNode* pNode = head;
        while(pNode!= nullptr){
            //判斷是否有相同節(jié)點
            if (pNode->next != nullptr && (pNode->val == pNode->next->val)){
                int val = pNode->val;
                while(pNode != nullptr && (pNode->val == val))
                        pNode = pNode->next;//找到下一個不同節(jié)點 
                preNode->next = pNode;
            }
            else{
                preNode = pNode;
                pNode = pNode->next;
            } 
        }
        return prehead->next; 
    }
};

Remove Duplicates from Sorted List

題目：Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2
Output: 1->2

遍歷整個鏈表，碰到下一節(jié)點的值相同，則定義下一結(jié)點指針，循環(huán)找到值不同的指針，最后該指針指向循環(huán)后的節(jié)點。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* Node = head;
        while(Node != nullptr){
            if (Node->next != nullptr && (Node->val == Node->next->val)){
                ListNode* pNode = Node->next;
                while (pNode->next != nullptr && (pNode->next->val == pNode->val))
                    pNode = pNode->next;
                Node->next = pNode->next; 
            }
            Node = Node->next;
        }
        return head;
    }
};

Partition List

題目：給定一個鏈表和一個值，要求小于這個值的結(jié)點都位于大于或等于這個值節(jié)點的前面。且保留原始節(jié)點相對位置。
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
思路：1）找到大于給定值的第一個節(jié)點，記錄該節(jié)點和上一結(jié)點。2）從該節(jié)點開始遍歷，遇到小于給定值的節(jié)點，將插入到記錄節(jié)點的前面。ps：中間涉及到四個指針。

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == nullptr)
            return nullptr;
        ListNode* p1 =head; 
        ListNode* p1Pre = nullptr;
        while(p1->val < x){ 
            p1Pre = p1;
            p1 = p1->next;
            if (p1 ==nullptr)
                return head;
        }
        ListNode* p2 = p1; 
        ListNode* p2Pre = p1Pre;
        while(p2 != nullptr){
            if(p2->val < x){
                if (p1Pre == nullptr)
                     head = p2; 
                else
                    p1Pre->next = p2; 
                p2Pre->next = p2->next;
                p2->next = p1;
                p1Pre = p2; 
                p2 = p2Pre->next; 
            }
            else{
                p2Pre = p2;
                p2 = p2->next;
            }
        }
        return head; 
    }
};

Swap Nodes in Pairs

題目：Given a linked list, swap every two adjacent nodes and return its head.
Example: Given 1->2->3->4, you should return the list as 2->1->4->3.
思路：三個指針。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* p1 = head;
        ListNode* p1Pre = nullptr;
        if (p1 == nullptr ||p1->next ==nullptr)
            return head;
        ListNode* p2 = p1->next;
        while(p2 !=nullptr){
            p1->next = p2->next; 
            p2->next = p1;
            if (p1Pre == nullptr) 
                head = p2;
            else
                p1Pre->next = p2;
            p1Pre = p1;
            p1 = p1->next;
            if(p1 == nullptr)
                return head;
            else
                p2 = p1->next;
        }
        return head;
    }
};

Rotate List

題目：Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
思路：由于有周期，先計算一個周期內(nèi)的K值。然后兩個指針循環(huán)使用，指向最后一個結(jié)點和倒數(shù)第二個節(jié)點。

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == nullptr)
            return nullptr;  
        ListNode* pNode = head;
        int count =1;
        while(pNode->next !=nullptr){
            count++;
            pNode = pNode->next;
        }
        k = k%count;
        while(k-- !=0){
            pNode = head;
            ListNode* preNode = nullptr;
            while(pNode->next != nullptr){
                preNode = pNode;
                pNode = pNode->next;
            }
            if(preNode == nullptr)
                return head;
            else
                preNode->next = nullptr;
            pNode->next = head;
            head = pNode; 
        } 
        return head;
    }
};

Reverse Linked List II

題目：Reverse a linked list from position m to n. Do it in one-pass.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
思路：1）首先找到并記錄第m,m-1個結(jié)點；2)然后反轉(zhuǎn)接下來的節(jié)點，直到第m個節(jié)點，同時可得到第n個節(jié)點和第n+1個節(jié)點；3）最后進行連接：m-1->next = n;m->next = n+1; pS：反轉(zhuǎn)鏈表中有涉及到三個指針。

//leetcode，鏈表的第m個節(jié)點到第n個節(jié)點區(qū)間反轉(zhuǎn)。
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {

        ListNode* helper = new ListNode(0);
        helper->next = head;
        ListNode* pNode = head;
        ListNode* preNode = helper; 
        int length = n-m;
        while(((m--)-1 ) && (pNode != nullptr)){
            preNode =pNode;
            pNode = pNode->next;
        } 
        if(head == nullptr || pNode == nullptr)
            return head;
        ListNode* reversestart = pNode;  
        ListNode* reversePre = preNode;
        ListNode* pNext = nullptr; 
        while(pNode !=nullptr){ 
            pNext = pNode->next;
            pNode->next = preNode; 
            if (!length--) 
                break;
            else{
                preNode = pNode;
                pNode = pNext;
            } 
        } 
        reversePre->next = pNode;
        reversestart->next = pNext;
        return helper->next;
    }
};

網(wǎng)易游戲-好友上下線排序（留著解決）

#include <iostream>
#include <cstdio>
#include<string>

using namespace std;

struct ListNode {
     string val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

ListNode* removeNode(ListNode* phead,opName){
    ListNode* pNode = phead;
    ListNode* preNode = nullptr;
    while(pNode!= nullptr){
        preNode = pNode;
        pNode= pNode->next;
    }
    if(preNode != nullptr)
        preNode->next = pNode->next;
    return pNode;
}

ListNode* addNode(ListNode* phead, ListNode* addNode){
    ListNode* helper = new ListNode('0');
    helper->next = phead;
    ListNode* pNode = phead;
    ListNode* preNode = helper;
    while(pNode!=nullptr){
        while(mapping[pNode->val] < mapping[addNode->val]){
            preNode = pNode;
            pNode = pNode->next;
        }
        while(pNode->val > addNode->val){
            preNode = pNode;
            pNode = pNode->next;
        }
        preNode->next = addNode;
        addNode->next = pNode;
    }
    return helper->next;
} 

int main(){
    //freopen("1.in","r",stdin);
    int n;
    cin >> n;
   string opName;
   int authority;
   map<string,int>mapping;
   ListNode* helper =  new ListNode('0');
   helper_>next = nullptr;
   while(n--){ 
       cin>>opName>>authority;
       mapping[opName] = authority;
       
       ListNode* people = new ListNode(opName);
       ListNode* preNode = helper;  
       ListNode *pNode = helper->next; 
       while(pNode!= nullptr && pNode->val > people->val){
            preNode = pNode;
            pNode = pNode->next;
       } 
       if(helper->next == nullptr)
           helper->next = people;
       preNode->next = people;
       people->next = pNode;
   }
   
    ListNode *onlineList = nullptr;
    ListNode *offlineList = helper->next;
    string opname;
    int op;
    where(M--){
        cin>>opName>>op;
        if(op == 1){
            ListNode* pNode = removeNode(offlineList,opName);
            onlineList = addNode(onlineList,pNode)；
        }
        else{
            ListNode* pNode = removeNode(onlineList,opName);
            offlineList = addNode(offlineList,pNode)；
        }
    }
    ListNode *pNode = onlineList;
    while(pNode != nullptr){
         cout<<pNode->val<<endl;
         pNode = pNode->next;
    }
    pNode = offlineList;
    while(pNode != nullptr){
         cout<<pNode->val<<endl;
         pNode = pNode->next;
    } 
}