链表相关面试题第二篇

朱雀 2023-01-21 02:28 21阅读 0赞

![在这里插入图片描述][resize_m_lfit_w_962_pic_center]

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、合并有序链表
 *   *   *  1.题目描述
         *  2.解题思路
 *  二、链表分割
 *   *   *  1.题目描述
         *  2.解题思路
 *  三、链表回文结构
 *   *   *  1.题目描述
         *  2.解题思路
 *  四、链表公共节点
 *   *   *  1.题目描述
         *  2.解题思路
 *  总结

--------------------

# 前言 #

--------------------

![在这里插入图片描述][20210514100351705.png_pic_left]

# 一、合并有序链表 #

[合并两个有序链表][Link 1]

### 1.题目描述 ###

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210514100700553.png]  
![在这里插入图片描述][20210514100709325.png]

### 2.解题思路 ###

1.  取两个链表中值小的一个当为头节点
2.  然后一直取两个链表中小的节点尾插到头节点后面
3.  注意判断结束条件

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]  
代码如下：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
    
    
    struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
    { 
        if(l1==NULL)
        { 
            return l2;
        }
        if(l2==NULL)
        { 
            return l1;
        }
        struct ListNode* head=NULL,*tail=NULL;
        if(l1->val<l2->val)
        { 
            head=tail=l1;
            l1=l1->next;
        }
        else
        { 
            head=tail=l2;
            l2=l2->next;
        }
        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)
        { 
            tail->next=l1;
        }
        if(l2)
        { 
            tail->next=l2;
        }
        return head;
    }

# 二、链表分割 #

[链表分割][Link 2]

### 1.题目描述 ###

现有一链表的头指针 ListNode\* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。  
![在这里插入图片描述][20210514101305164.png]  
![在这里插入图片描述][20210514101315315.png]

### 2.解题思路 ###

1.  把小于k值得链表分一个链表，大于k的值分为一个链表，最后把两个链表链接起来。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]  
    代码如下：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/
    class Partition { 
    public:
        ListNode* partition(ListNode* pHead, int x) 
        { 
            // write code here
            //两个哨兵节点greatHead，lessHead
            struct ListNode* lessHead=NULL,*lessTail=NULL;
            struct ListNode* greatHead=NULL,*greatTail=NULL;
            lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
            greatHead=greatTail=(struct ListNode*)malloc(sizeof(struct ListNode));
            struct ListNode* cur=pHead;
            while(cur)
            { 
                if(cur->val<x)
                { 
                    lessTail->next=cur;
                    lessTail=lessTail->next;
                }
                else
                { 
                    greatTail->next=cur;
                    greatTail=greatTail->next;
                }
                cur=cur->next;
            }
            lessTail->next=greatHead->next;
            greatTail->next=NULL;
            pHead=lessHead->next;
            free(lessHead);
            free(greatHead);
            return  pHead;
        }
    };

# 三、链表回文结构 #

[链表的回文结构][Link 3]

### 1.题目描述 ###

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。  
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。  
![在这里插入图片描述][20210514101534818.png]

### 2.解题思路 ###

1.  链表回文无非就是链表是否对称 ，可以先找链表的中间节点
2.  把中间节点之后的节点逆置一遍
3.  在把前面的节点值和链表后面的节点值相比较即可  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]  
    代码如下：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/
    class PalindromeList { 
    public:
        //1.先找中间节点
        //逆置中间结点后面的结点
        //头结点到中间结点前面一个和中间结点后面的结点值相比较
        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;
        }
        struct ListNode* reverse(struct ListNode* head)
        { 
            struct ListNode* cur=head;
            struct ListNode* newhead=NULL;
            while(cur)
            { 
                struct ListNode* next=cur->next;
                cur->next=newhead;
                newhead=cur;
                cur=next;
            }
            return newhead;
        }
        
        bool chkPalindrome(ListNode* A)
        { 
            struct ListNode* mid=middleNode(A);
            struct ListNode* rhead=reverse(mid);
            while(A&&rhead)
            { 
                if(A->val!=rhead->val)
                { 
                    return false;
                }
                else
                { 
                    A=A->next;
                    rhead=rhead->next;
                }
            }
            return true;
        }
    };

# 四、链表公共节点 #

[相交链表][Link 4]

### 1.题目描述 ###

编写一个程序，找到两个单链表相交的起始节点。  
如下面的两个链表：  
![在这里插入图片描述][20210514102102472.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]

### 2.解题思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]

1.  遍历分别求出两个链表的长度
2.  计算两个链表相差的长度
3.  长的链表先走相差的长度
4.  两个链表一起走
5.  如果有节点的地址相同，则返回，否则没有  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 8]  
    代码如下：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
     #include<math.h>
    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
    { 
        if(headA==NULL||headB==NULL)
        { 
            return NULL;
        }
        struct ListNode* curA=headA,*curB=headB;
        int lenA=0;
        int lenB=0;
        while(curA->next)
        { 
            lenA++;
            curA=curA->next;
        }
        while(curB->next)
        { 
            lenB++;
            curB=curB->next;
        }
        if(curA!=curB)
        { 
            return NULL;
        }
        struct ListNode* longList=headA,*shortList=headB;
        if(lenB>lenA)
        { 
            longList=headB;
            shortList=headA;
        }
        int gap=abs(lenA-lenB);
        while(gap--)
        { 
            longList=longList->next;
        }
        while(longList!=shortList)
        { 
            longList=longList->next;
            shortList=shortList->next;
        }
        return longList;
    }

--------------------

# 总结 #

以上就是今天要讲的内容，本文仅仅简单介绍了链表几道经典题的解法，后面会继续发布链表后面的题目解法，希望大家多多支持。还有，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。  
![在这里插入图片描述][resize_m_lfit_w_962_pic_center 1]

[resize_m_lfit_w_962_pic_center]: /images/20221021/1322456879f5444ba0b97c0303a77a4f.png
[20210514100351705.png_pic_left]: /images/20221021/23985fe81e504ae4af246a73e014cc50.png
[Link 1]: https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221021/62c81244fe86414f84a50d8c26fd772f.png
[20210514100700553.png]: /images/20221021/9b435de079714d6db9b682b6cca96c30.png
[20210514100709325.png]: /images/20221021/d13f98804c6d468a98666b6743b124fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221021/733fd35854e843e6bddb75a0df8ff8b1.png
[Link 2]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking&tab=answerKey
[20210514101305164.png]: /images/20221021/f802774b33704fa5b9cf31a850d89e6b.png
[20210514101315315.png]: /images/20221021/d1ddccbb15eb457887581315e4eac0ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221021/892e9dbba77b44b0b47be6e8a06986e6.png
[Link 3]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking&tab=answerKey
[20210514101534818.png]: /images/20221021/085a04911d7649d1b65b18e849a6248e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221021/7ad3d27e2e6c4af68076b73ce93bed80.png
[Link 4]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/
[20210514102102472.png]: /images/20221021/dd87f83f2e4140d1a6eeccc693566210.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]: /images/20221021/33e21c6463f04d51bb6abdf24446bb04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]: /images/20221021/47af426a10b64b8f8dc0d93615e216f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]: /images/20221021/8f0acd95b66d42058081a79a6f2f4f78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]: /images/20221021/f272372c66554e628031863e5a3c1730.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 8]: /images/20221021/cf5d147699ed4d8e990365b9b6972ce2.png
[resize_m_lfit_w_962_pic_center 1]: /images/20221021/1e5fd4370cdf4b229d034a9ea8122a38.png