单链表经典题总结

这些例题具体的解法并不重要，重要的是找到有什么是之前不会的，学习之后会了的。

掌握解决问题的技巧是关键的，再做题中会发现很多没有思路或者有但只有一点思路的题，这个时候打开电脑自带的画图工具画图思考是解决问题关键的一步。

思考所有可能的方法，以免钻牛角尖。

考虑常见的边界情况（对单链表而言是，头尾，空，非空）,完善代码。

积累做题的技巧，对于第一次见到的题目可以不会，但是第3次见到类似的题目就一定要做出来。

下面的OJ题是基于单链表的增删查改上的提升

下面做题一定要做三件事：

画图！画图！！画图！！！

 

 1. 删除链表中等于给定值 val 的所有节点。

力扣

注意几种情况:

head为空；一上来就要删除要改变头指针(注意可能会出现空指针的解引用)；连续的几个数都要删除;常规情况。

先写出常规的情况再看常规情况是否可以满足上述情况。

struct ListNode* removeElements(struct ListNode* head, int val){

    //如果一上来就要删除
    while(head&&head->val==val)
    {
        struct ListNode* next = head->next;
        free(head);
        head = next;
    }
    struct ListNode*prev = NULL,*cur = head;
    while(cur)
    {
        //如果要连续删除
        if(cur->val==val)
        {
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
        
    }
    return head;
}

如果图也画了，不同情况也考虑了但是走不过就进行调试。

有以下几种方法 ：

1.走读代码，用大脑走读

2.用图去走读。

画图严格跟着写的代码去走。

3.vs编译器上去调试（迫不得已别用）。

接口型的代码要自己创建一个情景再去调试。

2. 反转一个单链表。

力扣 

 

第一种方法：新头头插

遍历上面的链表把节点拿下来头插。

struct ListNode* reverseList(struct ListNode* head){
    
    struct ListNode* newhead = NULL;
    while(head)
    {
        struct ListNode* next = head->next;
        head->next = newhead;
        newhead = head;
        head = next;
    }
    return newhead;
}

第二种方法：3指针

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*n1=NULL,*n2 = head,*n3 = NULL;
    while(n2)
    {
        n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
    }
    return n1;
}

 下面的代码会崩，原因是再n3=NULL,对NULL进行了解引用

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*n1=NULL,*n2 = head,*n3 = NULL;
    while(n2)
    {
        
        n2->next = n1;
        n1 = n2;
        n3 = n3->next;
    }
    return n1;
} 

所以在迭代的时候还是先把下一个节点用cur/n2的方式保存下来，不要让它自己迭代。

 

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个 中间结点。

力扣 

 

注意本题用快慢指针解题时，要注意fast的结束条件当节点数时偶数时fast==NULL结束，奇数时fast->next==NULL就结束,但在写循环条件的时候还要注意循环条件时fast&&fast->next,不敢写成fast->next&&fast,fast不为空时第二个的前提。

如果fast==NULL了就会报一个空指针解引用错误，牛客会报段错误。

。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*fast = head,*slow= head;
    while(fast&&fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

类似的单链表指针一次走两步的问题都要考虑奇数偶数 。

4. 输入一个链表，输出该链表中倒数第k个结点。

链表中倒数第k个结点_牛客题霸_牛客网 

 

法一：要求倒数第k个就是求的时整数第n-k个

 法二：快慢指针：fast先走k步，再一起走

注意：

走k步和走k-1步判断结束的条件是不一样的。

走k步时fast走到NULL，走k-1步时fast->next==NULL

 用while(k--)这样的循环时，k在跳出循环的时候时-1而不是0，因为在k=0的时候k又减减了一次

while(k--)走了k步，while(--k)走了k-1步

struct ListNode* FindKthToTail(struct ListNode* head, int k ) {
    struct ListNode* slow=head,*fast = head;
    while(fast&&k--)
    {
        fast = fast->next;
    }
    if(k>0)
    {
        return NULL;
    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

5. 将两个有序链表合并为一个新的有序链表并返回。

新链表是通过拼接给定的两个链表的所有节点组成 的。

力扣 

 

哨兵位是个好东西，有了它上来就可以尾插不用管新头和尾是不是为空

先看一个不加哨兵位的解法： 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//传进来的链表有一个是空，就没必要再进行下一步了
    if(list1==NULL)
    return list2;
    if(list2==NULL)
    return list1;
//建立一个尾节点，方便尾插
    struct ListNode*newhead=NULL,*tail = NULL;
//取小的尾插
//只要有一个链表到头了就不用再进行尾插
    while(list1&&list2)
    {
        struct ListNode*newnode = NULL;
        if(list1->valval)
        {
            newnode = list1;
            list1 = list1->next;
        }
        else
        {
            newnode = list2;
            list2 = list2->next;
        }
        if(newhead==NULL)
        {
            newhead = tail = newnode;
        }
        else
        {
            tail->next = newnode;
            tail = newnode;
        }
    }
//把没有到头的链表剩下的部分尾插到新链表的尾
    if(list1)
    {
        tail->next = list1;
    }
    if(list2)
    {
        tail->next = list2;
    }
    return newhead;
}

 看一个有哨兵位的：

 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1==NULL)
    return list2;
    if(list2==NULL)
    return list1;
    struct ListNode* newhead,*tail;
    tail = newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newhead->next = NULL;
    while(list1&&list2)
    {
        if(list1->valval)
        {
            tail->next = list1;
            tail = list1;
            list1 = list1->next; 
        }
        else
        {
            tail->next = list2;
            tail = list2;
            list2 = list2->next; 
        }
    }
    if(list1)
    tail->next = list1;
    if(list2)
    tail->next = list2;
    struct ListNode*A = newhead->next;
    free(newhead);
    return A;
 }

本质还是链表的增删查改 

当然哨兵位的好处不只是帮助简化代码，还可以避免复杂情况的讨论。

 

 6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

链表分割_牛客题霸_牛客网

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
//遍历原链表把大于x的尾插到一个链表，小于x的尾插另一个链表，再和前面的题一样，lesstail->next = //greaterhead->next;
        ListNode*lesshead,*lesstail,*greaterhead,*greatertail;
        lesstail = lesshead = (ListNode*)malloc(sizeof(ListNode));
        greatertail = greaterhead = (ListNode*)malloc(sizeof(ListNode));
        while(pHead)
        {
            if(pHead->valnext;
                lesstail->next = pHead;
                lesstail = pHead;
                pHead = next;
            }
            else
            {
                ListNode*next = pHead->next;
                greatertail->next = pHead;
                greatertail = pHead;
                pHead = next;
            }
        }
        greatertail->next = NULL;
        lesstail->next = greaterhead->next;
        ListNode*newhead = lesshead->next;
        free(greaterhead);
        free(lesshead);
        greaterhead = lesshead = NULL;
        return newhead;
            }
};

如果不用哨兵位头节点的话要考虑很多的情况，如：全都是小于x的数，全都是大于x的数，pHead为空。

如果没有把greatertail->next=NULL，牛客会报一个内存超限，大概率是有死循环。

在链表中大概率是成环或者迭代的时候忘了cur = cur->next导致了死循环。

ListNode* partition(ListNode* pHead, int x) {
        if(pHead==NULL)
        {
            return NULL;
        }
        ListNode*lesshead,*lesstail,*greaterhead,*greatertail;
        lesstail = lesshead = greaterhead = greatertail = NULL;
        while(pHead)
        {
            ListNode*node = NULL;
            if(pHead->valnext;
                if(lesshead==NULL)
                {
                    lesshead = lesstail = node;
                }
                else
                {
                    lesstail->next = node;
                    lesstail = node;
                }
            }
            else
            {
                node = pHead;
                pHead = pHead->next;
                if(greaterhead==NULL)
                {
                    greaterhead = greatertail = node;
                }
                else
                {
                    greatertail->next = node;
                    greatertail = node;
                }
            }
        }
        //正常情况：
        if(lesshead&&greaterhead)
        {
            greatertail->next=NULL;
            lesstail->next = greaterhead;
            return lesshead;
        }
        //全是大于x的
        else if(lesshead==NULL)
        {
            return greaterhead;
        }
        //全是小于x的
        else if(greaterhead==NULL)
        {
            return lesshead;
        }
        return NULL;

其实也就是这样的差别，哨兵位头节点省脑子。

 

 7. 链表的回文结构。

链表的回文结构_牛客题霸_牛客网

牛客网上这个题可以遍历一遍用数组把数都存下来，把他当作顺序表中的回文问题。

 但是这是取了巧，下面看看正经的方法：

对于这个题，单链表无法像顺序表或者双向链表一样可以倒着走，所以逆置就成了解决问题的好的方法。

清楚了这一点下面的内容也就明了了：

找到中间节点，逆置后面的节点，再一一比较。

  bool chkPalindrome(ListNode* A) {
        // write code here
        //找到中间节点，逆置它后面的，一一比较
        
        ListNode*fast = A,*slow = A;
        while(fast&&fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode*mid = slow,*rhead = NULL;
        while(mid)
        {
            ListNode*next = mid->next;
            mid->next = rhead;
            rhead = mid;
            mid = next;
        }
        while(rhead&&A)
        {
            if(rhead->val==A->val)
            {
                rhead = rhead->next,A = A->next;
            }
            else
            {
                return 0;
            }
        }
        return 1;
    }

但是要注意的是逆置完了后的结构,奇数个节点自然没有问题：

 

偶数个节点是这样的：

 

 可以看出来rhead与A是没有完全断开的，叫做链表的相交。

但是这个题而言，这样的结构并不影响找回文结构。

其他题目中最好还是找到mid的前一个prev，把prev->next=NULL。

这个题也提醒我们，画图真的很重要。

8. 输入两个链表，找出它们的第一个公共结点。

力扣 

 

 可以暴力一点，，时间复杂度是o(N*M)的算法

下面看另一种：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //先看看有没又交点，找尾就可以判断，顺便查一下每个链表有几个节点
    struct ListNode *tailA = headA,*tailB = headB;
    int lenA = 1,lenB = 1;//因为在找尾的过程中记录长度所以不会记录最后一个，故而从1开始
    while(tailA->next)
    {
        tailA = tailA->next;
        lenA++;
    }
    while(tailB->next)
    {
        tailB = tailB->next;
        lenB++;
    }
    if(tailA!=tailB)
    {
        return NULL;
    }
    //如果这两个链表和前面说的回文链表一样，通过某种方法使之到公共节点的距离一样就好了
    //这就要用上刚刚记录的len了，让长的链表先走差距步，再一起走，第一个地址相同的节点就是。


    int grap = abs(lenA-lenB);
    //可以写if..else来进行分类讨论，但是有些繁琐所以此处定义两个新的指针,并尝试赋值
    struct ListNode *longList = headA,*shortList = headB;
    if(lenAnext;
    }
    while(longList&&shortList)
    {
        if(longList==shortList)
        return longList;
        longList = longList->next;
        shortList = shortList->next;
    }
    return NULL;
}

最后放一个综合题收尾： 

11. 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深度拷贝。

力扣 

 

 

 

 

 

 

struct Node* copyRandomList(struct Node* head) {
    //复制节点到源节点后面，配置random，拆除复制的节点
	struct Node*cur = head;
    while(cur)
    {
        struct Node*newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->val = cur->val;
        newnode->next = cur->next;
        cur->next = newnode;
        cur = cur->next->next;
    }
    cur = head;
    while(cur)
    {
        struct Node*copy = cur->next;
       
        if(cur->random)
        copy->random = cur->random->next;
        else
        {
            copy->random = NULL;
        }
        cur = copy->next;
    }
    cur = head;
   struct Node*copyHead = NULL,*copyTail = NULL;
    while(cur)
    {
        struct Node*copy = cur->next;
        cur->next = copy->next;
        if(copyHead==NULL)
        {
            copyHead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }
        cur = cur->next;
    }
    return copyHead;
}