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;}