手撕链表

作者: 熊大状 | 来源:发表于2018-08-08 10:01 被阅读4次

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

考察链表的题目不会要求我们时间复杂度，因为链表并不像是数组那样，可以方便的使用各种排序算法和查找算法。
因为链表涉及到大量的指针操作，所以链表的题目考察的主要是两个方面：代码的鲁棒性和简洁性。
不要一开始想到思路就开始写代码，最好是先想好测试用例，然后再让自己的代码通过所有的测试用例。
创建节点：ListNode* node= new ListNode();
删除删除节点：delete node; node = nullptr

【面试题05：从尾到头打印链表】

题目：输入个链表的头结点，从尾到头反过来打印出每个结点的值。
思路： 1、栈。入栈节点；出栈打印。 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)时间删除链表结点】

题目：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。

分类：
1、如果要删除的结点位于链表的尾部，那么它就没有下一个结点，这时我们就必须从链表的头结点开始，顺序遍历得到该结点的前序结点，并完成删除操作。pNode->next = nullptr; delete pToBeDeleted; pToBeDeleted = nullptr;
2、如果链表中只有一个结点，而我们又要删除链表的头结点，也就是尾结点，delete pToBeDeleted; pToBeDeleted = nullptr; *pHead=nullptr。
3、一般情况，记录下一节点，复制到该节点，并删除下一节点。

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;
    }
    //链表只有一个结点，删除头结点（也是尾结点）
    else if(*pListHead == pToBeDeleted)
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;
        *pListHead = NULL;
    }
    //要删除的结点是尾结点
    else{
        ListNode* pNode = *pListHead;
        while (pNode->m_pNext != pToBeDeleted) 
            pNode = pNode->m_pNext;

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

【面试题15：链表中倒数第k个结点】 Remove Nth Node From End of List

分三种情况：
1、空链表以及n=0，无效返回nullptr;
2、计算节点间隔，定义快节点（并判断n值是否有效），然后通过遍历快慢节点，确定待删节点
1、待删节点为头结点；
2、非头节点；ps：删除节点

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值是否在有效区间内
        while(p1 != nullptr){
            p1 = p1->next; 
            p2Pre = p2;
            p2 = p2->next;
        }//同步遍历，并记录删除节点的上一节点
        if(p2Pre == nullptr){
            head = p2->next;
        }
        else{
            p2Pre->next = p2->next;
        }//判断删除节点是否为首节点 
        free(p2);//删除节点；
        return head;
       
    }
};

链表有环问题：是否有环Linked List Cycle，环入口节点

用两个指针去遍历，一个指针一次走两步，一个指针一次走一步，如果有环，两个指针肯定会在环中相遇。相遇点即为环内某个节点。时间复杂度为O（n）。
环入口两种思路：
1、采用两个指针，一快一慢相隔环长度节点，相遇即为入口节点。环长度根据上面判断是否有环的相遇点计算，相遇点出发到在此回到该节点时计数。
2、在上面的相遇节点处断开（当然函数结束时不能破坏原链表），这样就形成了两个相交的单链表，求进入环中的第一个节点也就转换成了求两个单链表相交的第一个节点。

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） 确定有无环
    #2） 确定环节点数
    #3） 确定环入口节点*/
    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：反转链表】

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

需记录三个节点。可以采用辅助结点，避免考虑头结点情况。一般需要考虑当前节点的上一结点时可采用辅助头结点。

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

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的

每次取两个链表的头结点进行比较；剩下的两个链表仍是排序链表，属于递归问题。

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：复杂链表的复制】

题目：请实现函数ComplexListNode clone(ComplexListNode head),复制一个复杂链表。在复杂链表中，每个结点除了有一个next 域指向下一个结点外，还有一个sibling 指向链表中的任意结点或者null。

1、两步：第一步复制顺序节点，第二部复制随机节点，节点的定位需要O(n)。总的时间复杂度O(nn)。
2、三步：顺序节点的复制，并顺序连接在该节点的后面；随机节点的复制根据原节点的定位；奇偶拆分链表。时间复杂度O(n).
ps：完成第一步的顺序节点复制，才能定位之后的随机节点；生成节点: 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;
    }
};

查找单链表的中间结点

典型的两个指针问题。定义两个指针，快指针一次走两步，慢指针一次走一步。快指针走到最后一个节点，慢指针对应的就是中间节点

【面试题37：两个链表的第一个公共结点】 intersection-of-two-linked-lists

题目：输入两个链表，找出它们的第一个公共结点。

第一个问题：是否相交。如果相交两个链表的尾节点一定相同。
第二个问题：第一个相交公共点。
1、异步遍历找相同节点。时间复杂度O(mn)
2、第一公共节点后两链表重合，从后往前遍历。采用后进先出（栈）。栈的定义：std::stack<ListNode*>nodes。时间复杂度O(m+n)，空间复杂度O(m+n)
3、先计算两链表长度差，让长链表先走差步，然后同步遍历两链表找到第一个相同节点。时间复杂度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.
思路：逐节点相加。注意点：1）进位问题，2）链表长短不一，3）两链表遍历完后可能仍有进位，还需循环一次。

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

题目：删除链表中重复的节点。
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5

1）第一个节点就为待删除节点；
2）中间节点待删除；
3）尾节点待删除
ps:增加一个头节点，不许考虑第一个节点待删除的情况。

// 三种情况：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){
            //判断是否有相同节点
            if (pNode->next != nullptr && (pNode->val == pNode->next->val)){
                int val = pNode->val;
                while(pNode != nullptr && (pNode->val == val))
                        pNode = pNode->next;//找到下一个不同节点
                if(preNode == nullptr)//如果重复节点被头指针指向
                    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){
            //判断是否有相同节点
            if (pNode->next != nullptr && (pNode->val == pNode->next->val)){
                int val = pNode->val;
                while(pNode != nullptr && (pNode->val == val))
                        pNode = pNode->next;//找到下一个不同节点 
                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

遍历整个链表，碰到下一节点的值相同，则定义下一结点指针，循环找到值不同的指针，最后该指针指向循环后的节点。

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

题目：给定一个链表和一个值，要求小于这个值的结点都位于大于或等于这个值节点的前面。且保留原始节点相对位置。
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
思路：1）找到大于给定值的第一个节点，记录该节点和上一结点。2）从该节点开始遍历，遇到小于给定值的节点，将插入到记录节点的前面。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
思路：由于有周期，先计算一个周期内的K值。然后两个指针循环使用，指向最后一个结点和倒数第二个节点。

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个结点；2)然后反转接下来的节点，直到第m个节点，同时可得到第n个节点和第n+1个节点；3）最后进行连接：m-1->next = n;m->next = n+1; pS：反转链表中有涉及到三个指针。

//leetcode，链表的第m个节点到第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;
    }
};

网易游戏-好友上下线排序（留着解决）

#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;
    } 
}