单链表oj (上)，详细的过程分析，每道题有多种解题思路，一定会有所收获

🧸🧸🧸各位巨佬大家好，我是猪皮兄弟🧸🧸🧸

这里是下面要讲的知识内容🥳🥳🥳

文章目录

🚒前言

链表中，单链表的oj是面试中最常考察的问题，单链表的解题逻辑也很有意思，下面一起来看看吧！

一、移除链表元素

leetcode移除链表元素

三种思路
1.需要一个prev指针，指向被删除结点的前一个，然后进行遍历
2.设置一个新的头，对需要保留的结点进行链接
3.malloc一个头节点，比方法一好控制一点

方法一

structListNode*removeElements(structListNode* head,int val){if(head==NULL)returnNULL;structListNode*prev=NULL,*cur=head;while(cur){if(cur->val==val){if(prev==NULL){
                head=cur->next;free(cur);
                cur=head;}else{
                prev->next=cur->next;free(cur);
                cur=prev->next;}}else{
            prev=cur;
            cur=cur->next;}}return head;}

方法二

structListNode*removeElements(structListNode* head,int val){if(head==NULL)returnNULL;structListNode*newhead=NULL;structListNode*tail=newhead;structListNode*cur=head;while(cur){if(cur->val!=val){if(newhead==NULL){
                newhead=tail=cur;}else{
                tail->next=cur;
                tail=cur;}}
        cur=cur->next;}if(newhead!=NULL)
    tail->next=NULL;return newhead;}

方法三

structListNode*removeElements(structListNode* head,int val){if(head==NULL)returnNULL;structListNode* Node=(structListNode*)malloc(sizeof(structListNode));
    Node->next=head;structListNode*prev=Node,*cur=head;while(cur){if(cur->val==val){if(cur==head){
                head=cur->next;free(cur);
                cur=head;}else{
                prev->next=cur->next;free(cur);
                cur=prev->next;}}else{
            prev=cur;
            cur=cur->next;}}free(Node);return head;}

二、反转链表

leetcode反转链表

两种思路
1.malloc一个头结点，然后设置三个临时的指针变量进行控制
2.设置一个新的头，遍历链表，每次都取下来连接到新的上，就可以实现反向

方法一

structListNode*reverseList(structListNode* head){if(head==NULL||head->next==NULL)return head;structListNode* Node=(structListNode*)malloc(sizeof(structListNode));
    Node->next=head;structListNode*n1,*n2,*n3;
    n1=Node;
    n2=head;
    n3=head->next;while(n2){
        n2->next=n1;
        n1=n2;
        n2=n3;if(n2)//控制边界条件
        n3=n3->next;}
    head->next=NULL;
    head=n1;free(Node);return head;}

方法二

structListNode*reverseList(structListNode* head){if(head==NULL||head->next==NULL)return head;structListNode*cur,*next,*newhead;
    cur=head;
    next=cur->next;
    newhead=NULL;while(cur){if(head==cur)
        cur->next=newhead;else{
            cur->next=newhead;}
        newhead=cur;
        cur=next;if(cur)
        next=next->next;}return newhead;}

三、倒数第n个结点

nowcoder倒数第n个结点

三种思路
1.两次遍历，计算链表长度来减去k次就是需要执行的长度
2.反转链表再遍历k个结点
3.快慢指针

方法一

structListNode*FindKthToTail(structListNode* pListHead,int k ){// write code hereint count=0;structListNode*cur=pListHead;while(cur){
        cur=cur->next;
        count++;}int runNum=count-k;
    count=0;
    cur=pListHead;while(cur){if(count==runNum){break;}
        count++;
        cur=cur->next;}return cur;}

方法二
就是反转一下链表再遍历k个就可以了，我就不写了
方法三
利用快慢指针

structListNode*FindKthToTail(structListNode* pListHead,int k ){// write code herestructListNode*fast,*slow;
    fast=pListHead;
    slow=NULL;int count=0;while(count!=k&&fast){
        fast=fast->next;
        count++;}if(count==k)
        slow=pListHead;while(fast){
        fast=fast->next;
        slow=slow->next;}return slow;}

四、合并有序链表

遍历两个链表即可

structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){if(!list1)return list2;if(!list2)return list1;structListNode*head;if(list1->val<list2->val){
        head=list1;
        list1=list1->next;}else{
        head=list2;
        list2=list2->next;}structListNode*tail=head;while(list1&&list2){if(list1->val<=list2->val){
            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;}return head;}

五、小总结

单链表的oj在面试当中出现频率是很高的，单链表有些操作也是很玄幻，跟着我一起来做题吧，后面还会继续更新🥳🥳🥳