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 herestruct 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、更新拷贝节点的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;
}

• 总代码如下：

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、更新拷贝节点的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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！