LeetCode每日一刷 — 手撕单链表习题（2）

目录

1、链表的回文结构

2、相交链表

3、复制带随机指针的链表

1、链表的回文结构

• 链接直达：

链表的回文结构

• 题目：

• 思路：

找中间节点再逆置，此法非常巧妙，找中间节点和逆置这两块内容在上一份博文中已经详细讲解过，这里不多赘述，这样做的原因是执行上述操作后遍历原头节点和逆置后新头节点，判断值是否相等，若遍历后都相等则返回true，反之false。

• 代码如下：

class PalindromeList {public://第一步：找到中间节点    struct ListNode* middleNode(struct ListNode* head) {        struct ListNode* slow = head;        struct ListNode* fast = head;        while (fast && fast->next)        {            slow = slow->next;            fast = fast->next->next;        }        return slow;    }//第二部：逆置从中间节点开始往后的数据，并返回新的头节点    struct ListNode* reverseList(struct ListNode* head) {        if (head == NULL)        {            return NULL;        }        struct ListNode* n1 = head;        struct ListNode* n2 = head->next;        struct ListNode* n3 = NULL;        while (n1)        {            n1->next = n3;            n3 = n1;            n1 = n2;            if (n2)            {                n2 = n2->next;            }        }        return n3;    }    bool chkPalindrome(ListNode* A) {        // write code here        struct ListNode* mid = middleNode(A);        struct ListNode* rHead = reverseList(mid);        while (A && rHead)        {            if (A->val == rHead->val)            {                A = A->next;                rHead = rHead->next;            }            else            {                return false;            }        }        return true;    }};

2、相交链表

• 链接直达：

相交链表

• 题目：

• 思路：

法一：A链表的每个元素跟B链表依次比较，如果有相等，就是相交，第一个相等的就是交点。

此法的时间复杂度是O(M*N)，此法的优势就是在判断好是否相交后直接把相交的节点求出来了，注意：在比较的时候不能拿值去比较，要拿地址去比较。此法的缺陷就是效率相对较低，可以再进行改进。

法二：遍历原链表 + 快慢指针

先判断两个链表是否相交

依次遍历两个链表到尾，看两个尾节点地址是否相同，若相同则一定相交。此时的时间复杂度就是O(M+N)，相较于法一可是优化了太多。

再找出第一个交点

执行完上一步知道了链表相交，接下来就要求交点了，先求出两个链表的长度La，Lb。再定义连个指针分别指向两个链表的头，让长度较长的链表指针先走 | La-Lb | 步，再让两个链表指针一起走，若发现地址存在相同，那么就停止，此时找到交点。这种情况的时间复杂度同样是O(M+N)。

• 代码如下：

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {    int lenA = 0;    int lenB = 0;    struct ListNode* cur1 = headA;    struct ListNode* cur2 = headB;    //1、判断是否相交    while (cur1->next)    {        cur1 = cur1->next;        lenA++;    }    while (cur2->next)    {        cur2 = cur2->next;        lenB++;    }    //若相交，进入if判断    if (cur1 == cur2)    {        struct ListNode* shortList = headA, * longList = headB;        if (lenA > lenB)        {            longList = headA;            shortList = headB;        }        int num = abs(lenA - lenB);        //让长的链表先走差距步        while (num--)        {            longList = longList->next;        }        while (shortList && longList)        {            if (shortList == longList)            {                return shortList;            }            //此时两链表一起走            else            {                shortList = shortList->next;                longList = longList->next;            }        }    }    //若不相交，则直接返回空    return NULL;}

3、复制带随机指针的链表

• 链接直达：

复制带随机指针的链表

• 题目：

• 思路：

法一：直接复制（malloc）+ 找相对距离

定义一个指针cur指向原链表第一个元素，cur指向第一个值为7，再malloc出一个7来，cur往后走，继续malloc，再尾插，以此遍历下去。新的链表复制出来了，关键在于如何处理新链表的random指针，这里可以采用找相对距离的方法，找原链表random指向第几个，那么新链表对应指向第几个。但是这个方法过于复杂，时间复杂度达到了O(N^2)。不是太推荐

法二：

首先，把拷贝节点链接在原节点后面

struct Node* cur = head;//1、拷贝节点链接在原节点后面while (cur){    struct Node* copy = (struct Node*)malloc(sizeof(struct Node));    copy->val = cur->val;    copy->next = cur->next;    cur->next = copy;    cur = cur->next->next;}

接着，链接拷贝节点的random在原节点random后面

比如我们拷贝出来的13这个数字，拷贝的13的random就是原头13的random的next。因为在原链表中，13的random指向7，现在想让拷贝出来的13的random指向拷贝出来的7。原链表中，7的next指向拷贝出的7，综上：拷贝的13的random就是原头13的random的next 。以此类推。

//2、更新拷贝节点的randomcur = head;while (cur){    struct Node* copy = cur->next;    if (cur->random == NULL)    {        copy->random = NULL;    }    else    {        copy->random = cur->random->next;    }    cur = cur->next->next;}

最后，恢复原链表，把拷贝链表链接在一起

//3、拷贝节点剪下来，链接到一起cur = head;struct Node* copyTail = NULL;struct Node* copyHead = NULL;while (cur){    struct Node* copy = cur->next;    struct Node* next = copy->next;    cur->next = next;    if (copyTail == NULL)    {        copyHead = copyTail = copy;    }    else    {        copyTail->next = copy;        copyTail = copyTail->next;    }    cur = next;}return copyHead;}

• 总代码如下：

struct Node* copyRandomList(struct Node* head) {    struct Node* cur = head;    //1、拷贝节点链接在原节点后面    while (cur)    {        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));        copy->val = cur->val;        copy->next = cur->next;        cur->next = copy;        cur = cur->next->next;    }    //2、更新拷贝节点的random    cur = head;    while (cur)    {        struct Node* copy = cur->next;        if (cur->random == NULL)        {            copy->random = NULL;        }        else        {            copy->random = cur->random->next;        }        cur = cur->next->next;    }    //3、拷贝节点剪下来，链接到一起    cur = head;    struct Node* copyTail = NULL;    struct Node* copyHead = NULL;    while (cur)    {        struct Node* copy = cur->next;        struct Node* next = copy->next;        cur->next = next;        if (copyTail == NULL)        {            copyHead = copyTail = copy;        }        else        {            copyTail->next = copy;            copyTail = copyTail->next;        }        cur = next;    }    return copyHead;}