目录

前言

1.移除链表元素

2.反转链表

3.链表的中间结点

4.链表中的倒数第K个结点 

5.合并两个@R_360_2506@ 

6.分割链表

7.回文链表

8.相交链表

9.环形链表

10.环形链表II

11.复制带随机指针的链表

---

前言

前面我们学习了链表，并实现了单链表，关于链表的OJ题在面试时也经常考到，学会了这些OJ题，链表对于你来说就是小菜一碟了。

1.移除链表元素

移除链表元素

这道题比较简单，依次遍历链表，如果该结点的值等于需要删除的值，直接删除掉该结点即可。

但需注意其中的特殊情况F1a;

1. 链表为空。
2. 头结点为需要删除结点。

tyPEdef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val){
    //考虑链表为空的情况
    if(head == NULL)
    {
        return NULL;
    }

    //链表不为空
    ListNode*cur = head;//用来遍历链表(一般不使用head遍历，这样会找不到头结点)
    ListNode*prev = NULL;//用来保存需要删除结点的前一个结点
    while(cur)
    {
        
        if(cur->val == val)
        {
            //头结点为需要删除的结点
            if(cur == head)
            {
                head = head->next;//将头结点右移
                free(cur);
                cur = head;
            }
            else
            {
                
                ListNode*next = cur->next;//保存下一个结点
                PRev->next = next;//将需要删除结点的前一个结点指向下一个结点
                free(cur);
                cur = next;
                //这里也可以不创建next变量
                //prev->next = cur->next;
                //free(cur);
                //cur = prev->next;
            }
        }
        else
        {
            prev = cur;//保存上一个节点
            cur = cur->next;//向右移动
        }
    }
    return head;
}

2.反转链表

反转链表

这里有两种方法：

1.三指针法：即创建三个指针n1,n2,n3，n1,n2用来反转两个结点，n3用来保存下一个结点的地址，反转后依次迭代直到n2为NULL。如图：

代码如下： 

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
    //因为后面head需要解引用所以必须要考虑链表为NULL的情况
    if(head==NULL)
    {
        return NULL;
    }

    ListNode*n1 = NULL;
    ListNode*n2 = head;
    ListNode*n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        //因为是以n2为NULL为循环结束条件，需保证n3不为NULL时，再迭代n3
        if(n3!=NULL)
        {
            n3 = n3->next;
        }
    }
    return n1;
}

2.头插法：即建立新的头结点，将原链表每个结点取下来头插到新头结点上，然后将新头结点左移。如图：

 代码如下：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
    ListNode*newhead = NULL;//这里不需要判断链表为NULL的情况，链表为NULL也能处理
    ListNode*cur = head;
    while(cur)
    {
        ListNode*next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

注：起始两种方法的代码非常类似，但思路却不相同。

3.链表的中间结点

链表的中间结点

方法：快慢指针

即慢指针一次走一步，快指针一次走两步，快指针走到NULL时慢指针会刚好到链表的中间结点。

如图：

@H_629_126@

 代码如下：

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head){
    ListNode*fast = head;
    ListNode*slow = head;
    while(fast&&fast->next)//循环结束条件为fast为NULL或fast->next为NULL
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

4.链表中的倒数第K个结点 

链表中的倒数第K个结点

方法：快慢指针

快指针先走K步，然后快慢指针同时走。直到快指针为NULL。

(注：这里的快指针一次走一步)

如图：

代码如下：

typedef struct ListNode ListNode;
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    ListNode*fast = head;
    ListNode*slow = head;
    while(k--)//fast先走
    {
        if(fast==NULL)//当K大于等于结点个数时，fast会走到NULL
        {
            return NULL;
        }
        fast = fast->next;
        
    }
    while(fast)//fast，slow同时走
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

5.合并两个有序链表 

和并两个有序链表

方法：创建头结点，依次比较两个链表每个结点的大小，将较小的结点尾插到头结点的后面。

注意：

1. 使用哨兵位的头结点会比较简单。
2. l1或l2中一个为NULL的情况。
3. 当两个链表不相等时，不要忘记将剩余结点连接到合并链表的后面。 

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    //l1为NULL
    if (l1 == NULL)
    {
        return l2;
    }

    //l2为NULL
    if (l2 == NULL)
    {
        return l1;
    }

    //都不为NULL
    ListNode*head = NULL;
    ListNode*tail = NULL; 
    head = tail =(ListNode*)malloc(sizeof(ListNode));//创建哨兵位头结点，即头结
                                                     //点不存放有效值.
    while(l1&&l2)
    {
        if(l1->val<l2->val)
        {
            tail->next = l1;
            l1 = l1->next;
        }
        else
        {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    //结点剩余情况
    if(l1==NULL)
    {
        tail->next = l2;
    }
    else
    {
        tail->next = l1;
    }

    //释放哨兵位头结点
    tail = head;
    head = head->next;
    free(tail);
    tail = NULL;
    return head;
}

哨兵位头结点：不保存有效值。

优点：连接结点时不需判断头结点是否为NULL，直接连接在头结点后面即可。

注意：返回时需返回头结点的下一个结点，且需释放哨兵位结点。

6.分割链表

分割链表

方法：创建两个头结点head1，head2，将小于x的结点尾插到head1后面；将大于等于x的结点尾插到head2的后面。（注意：不要改变原结点的顺序）

如图：

代码如下：

typedef struct ListNode ListNode;
struct ListNode* partITion(struct ListNode* head, int x){
    ListNode*head1 = (ListNode*)malloc(sizeof(ListNode));//创建两个哨兵位头结点
    ListNode*head2 = (ListNode*)malloc(sizeof(ListNode));
    head1->next = NULL;
    head2->next = NULL;
    ListNode*cur = head;//用来遍历原链表
    ListNode*tail1 = head1;//用来保存head1尾结点
    ListNode*tail2 = head2;//用来保存head2尾结点
    while(cur)
    {
        if(cur->val<x)//小于x尾插到head1链表
        {
            tail1->next = cur;
            tail1 = tail1->next;
        }
        else//大于等于x尾插到head2链表
        {
            tail2->next = cur;
            tail2 = tail2->next;
        }
        cur = cur->next;
    }
    tail2->next = NULL;//将head2链表的尾结点指向NULL，可能head2的尾结点还指向原链表中的结点，导致连接后链表成环。
    tail1->next = head2->next;//连接head1，head2链表
    ListNode*newhead = head1->next;//保存有效头结点
    free(head1);//释放哨兵位头结点
    free(head2);
    head1 = NULL;
    head2 = NULL;
    return newhead;
}

注意：若未将head2的尾结点的next指向NULL，则会出现一下情况：

7.回文链表

回文链表

方法：找到链表的中间结点，将链表一分为二，将前后任意部分反转，依次必将两部分链表每个结点是否相等。

注：

1. 链表结点为NULL或结点个数为0时返回true。
2. 链表结点个数为奇数个时，中间结点不会影响结果。

如图：

typedef struct ListNode ListNode;
bool isPalindrome(struct ListNode* head){
    //链表为空或链表只有一个结点的情况
    if(head==NULL||head->next==NULL)
    {
        return true;
    }

    //找中间结点    
    ListNode*fast = head;
    ListNode*slow = head;
    ListNode*prev = NULL;//保存前一个结点
    while(fast && fast->next)
    {
        prev = slow;
        fast = fast->next->next;
        slow = slow->next;
    }

    //断开两链表
    prev->next = NULL;

    //反转后面链表
    ListNode*newhead = NULL;
    while(slow)
    {
        ListNode*next =slow->next;
        slow->next = newhead;
        newhead = slow;
        slow = next;
    }

    //比较两链表每个结点
    while(head && newhead)//当链表结点个数为奇数时，两链表的长度不相等，所以只要有一个链表为空就结束循环
    {
        if(head->val != newhead->val)
        {
            return false;
        }
        head = head->next;
        newhead = newhead->next;
    }
    return true;

}

8.相交链表

相交链表

方法1(暴力求解)：依次将A链表中的每个结点与B链表的每个结点相比，直到A链表为NULL。

(@R_814_1304@：O(N^2))

代码如下：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* curA = headA;
    ListNode* curB = headB;
    while(curA)
    {
        while(curB)
        {
            if(curA == curB)
            {
                return curA;
            }
            curB = curB->next;
        }
        curA = curA->next;
        curB = headB;
    } 
    return NULL;
}

方法2：

1. 可先比较两链表的最后一个结点是否相等，若相等则两链表必相交，否则不相交。
2. 如果相交则先分别计算出A，B链表的长度，算出长度差。
3. 将较长链表先走差距步，然后两链表再同时走。
4. 判断依次判断结点是否相等。

代码如下：

 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* curA = headA;
    ListNode* curB = headB;
    int lenA = 1;
    int lenB = 1;

    //找到两链表的尾结点，顺便计算出两链表的长度
    while(curA->next)
    {
        curA = curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB = curB->next;
        lenB++;
    }

    //如果两链表尾结点不相等则两链表不相交
    if(curA!=curB)
    {
        return NULL;
    }

    //计算两链表长度差
    int gap = abs(lenA-lenB);
    
    //长链表先走差距步
    if(lenA>lenB)
    {
        while(gap--)
        {
            headA = headA->next;
        }
    }
    else
    {
        while(gap--)
        {
            headB = headB->next;
        }
    }

    //依次比较两链表的每个结点
    while(headA!=headB)
    {
        headA = headA->next;
        headB = headB->next;
    }
    return headA;
}

9.环形链表

环形链表

方法：快慢指针

快指针一次走两步，慢指针一次走一步，如果链表无环，则快指针会走到NULL；如果链表有环，快指针会先入环，慢指针后入环，在环内快指针会追上慢指针。

如图：

 代码如下：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        
        //链表有环，则循环不会结束，直到slow=fast返回true
        if(slow == fast)
        {
            return true;
        }
    }

    //链表无环，循环结束返回false
    return false;
}

10.环形链表II

环形链表II(返回链表入环点)

方法：快慢指针+公式运算

1. 根据快慢指针判断链表是否有环。
2. 如果有环，根据快指针走的路程等于慢指针走的路程的2倍。

如图：

代码如下：

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode*fast = head;
    ListNode*slow = head;

    //判断链表是否有环
    while(fast&&fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        //链表有环
        if(slow==fast)
        {
            
            //根据等式寻找入环点
            ListNode*cur = head;
            while(cur!=fast)
            {
                cur = cur->next;
                fast = fast->next;
            }
            return cur;
        }
    }
    return NULL;
}

面试官反问：

为什么fast和slow一定会在环中相遇？会不会错过？

为什么快指针一次要走两部，而不是走三步，四步......?

如图：

11.复制带随机指针的链表

复制带随机指针的链表

这个题的长度看着就有些劝退啊，但我们只要直到方法其实并不难。

可能有些人会觉得，诶不是直接将链表的每个结点拷贝一下就行了吗？

虽然我们直到拷贝之前的random，但拷贝之后的random的具体位置与拷贝之前是没有任何关系的，所以不能使用这种方法。

如何去复制一个带随机指针的链表？

首先我们可以忽略 random 指针，然后对原链表的每个节点进行复制，并追加到原节点的后面，而后复制 random 指针。最后我们把原链表和复制链表拆分出来，并将原链表复原。

图示过程如下：

1、在每个节点的后面加上它的复制，并将原链表和复制链表连在一起。

2、 从前往后遍历每一个原链表节点，对于有 random 指针的节点 p，我们让它的 p->next->random = p->random->next，这样我们就完成了对原链表 random 指针的复刻。

3、最后我们把原链表和复制链表拆分出来，并将原链表复原。

具体过程如下：

1. 定义一个 cur 指针，遍历整个链表，复制每个节点，并将原链表和复制链表连在一起。
2. 再次遍历整个链表，执行 newnode->random = cur->random->next，复制 random 指针。
3. 定义newhead 用来指向复制链表的头节点， 将两个链表拆分并复原原链表。

时间复杂度分析： O(n)O(n)，其中 n 是链表的长度。

代码如下：

typedef struct Node Node;
struct Node* copyRandoMList(struct Node* head) {
    //拷贝结点到原结点的后面
	Node*cur = head;
    while(cur)
    {
        Node*newnode = (Node*)malloc(sizeof(Node));
        Node*next = cur->next;
        cur->next = newnode;
        newnode->val = cur->val;
        newnode->next = next;
        cur = next;
    }

    //将拷贝结点的random连接到上一个结点的next
    cur = head;
    while(cur)
    {
        Node*copy = cur->next;
        Node*next = copy->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random =cur->random->next; 
        }
        cur = next;
    }

    //断开拷贝结点，恢复原链表
    cur = head;
    Node*newhead = (Node*)malloc(sizeof(Node));
    newhead->next= NULL;
    //newhead = head->next;
    Node*tail = newhead;
    while(cur)
    {
        Node*copy = cur->next;
        Node*next = copy->next;
        tail->next = copy;
        tail = copy;
        cur->next = next;
        cur = next;
    }
    Node*copyhead = newhead->next;
    free(newhead);
    newhead = NULL;
    return copyhead;
}

这些你学到了吗？