【链表】算法题（二） ----- 力扣/牛客

一、链表的回文结构

思路：

        找到链表的中间节点，然后逆置链表的后半部分，再一一遍历链表的前半部分和后半部分，判断是是否为回文结构。

快慢指针找到链表的中间节点

        slow指针指向的就是中间节点

逆置链表后半部分

        逆置链表后半部分

遍历链表前半部分和后半部分

        如果left和right指向的数据不相等，就跳出循环，返回false；如果遍历到left或者right为NULL，数据都相等，那么链表具有回文结构，返回true。

这里如果是奇数个节点：

遍历结束后：

class PalindromeList {
public://找链表中间节点ListNode* Listmid(ListNode* phead){ListNode* fast, *slow;fast=slow=phead;while(fast && fast->next){slow=slow->next;fast=fast->next;}return slow;}//逆置ListNode* reverse(ListNode* phead){ListNode* l1,*l2,*l3;l1=NULL;l2=phead;while(l2){l3=l2->next;l2->next=l1;l1=l2;l2=l3;}return l1;}bool chkPalindrome(ListNode* A) {// write code here//找到链表中间节点ListNode* mid=Listmid(A);//逆置后半部分ListNode* phead = reverse(mid);//比较ListNode* left, *right;left=A;right=phead;while(right && left){if(right->val!=left->val){return false;}left=left->next;right=right->next;}return true;}
};

二、相交链表

判断两个链表是否相交，如果相交就返回相交节点，如果链表不相交，那就返回NULL；

思路：

        先遍历两个链表，记录两个链表的节点个数；再同时遍历两个链表 ，让节点个数多的链表先往前走s（链表的节点个数差）；同时遍历两个链表，如果指向链表的指针相等，就返回当前节点；如果遍历链表结束后，都没有相等的节点，那就返回NULL。

typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {if (headA == NULL) {return NULL;}if (headB == NULL) {return NULL;}int sizeA = 0, sizeB = 0;ListNode *l1, *l2;l1 = headA;l2 = headB;while (l1) {sizeA++;l1 = l1->next;}while (l2) {sizeB++;l2 = l2->next;}ListNode* shortList = headA;ListNode* longList = headB;int s = abs(sizeA - sizeB);if (sizeA > sizeB) {shortList = headB;longList = headA;}while (s) {s--;longList = longList->next;}while (longList && shortList) {if (longList == shortList) {return longList;}longList = longList->next;shortList = shortList->next;}return NULL;
}

三、环形链表1

判断 链表中是否存在环，如果存在就返回true，如果不存在就返回false；

思路：快慢指针

        定义两个指针fast和slow；遍历链表，fast每次向前走两步，slow每次向前走一步，如果链表存在环，fast与slow指针一定会相遇；如果遍历链表，fast或者fast->next为NULL，则链表不存在环。

根据题目所给示例来分析一下：

        首先定义两个指针 fast  slow

        fast向前走两步，slow向前走一步

        fast向前走两步，slow向前走一步

        fast向前走两步，slow向前走一步

此时，fast和slow相遇，证明链表中存在环，返回true。

        如果链表不存在环结构，遍历过程中fast或者fast->next指针会等于NULL，将这个作为结束条件即可。

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* fast, *slow;fast=slow=head;while(fast && fast->next){fast=fast->next->next;slow=slow->next;if(slow == fast){return true;}}return false;
}

四、环形链表2

        上面只是让我们判断链表是否带环，这道题让我们返回链表环的起始节点，如果不存在环就返回NULL。

思路：

        使用快慢指针找到快慢指针的相遇节点；再定义两个指针从相遇节点和链表头结点开始遍历，两个指针相遇时的节点就是链表环的起始节点。

根据题目的示例来分析：

        先找到链表快慢指针的相遇节点：

        定义两个指针从链表头部和相遇节点开始遍历链表

        遍历链表直到两个指针相遇

        两个指针相遇，此时指针指向的节点就是链表环的起始节点。

typedef struct ListNode ListNode;
ListNode* hasCycle(struct ListNode *head) {ListNode* fast, *slow;fast=slow=head;while(fast && fast->next){fast=fast->next->next;slow=slow->next;if(slow == fast){return slow;}}return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) {//找到快慢指针相遇节点ListNode* pos=hasCycle(head);if(pos==NULL){return NULL;}//从头结点和相遇节点开始遍历ListNode* ptail=head;while(1){if(pos==ptail){return pos;}pos=pos->next;ptail=ptail->next;}
}

五、随机链表的复制

这里题目上提到了一个深拷贝

  思路：

        先在原链表的基础上创建节点，形成新的链表，再给链表节点的random指针赋值，最后断开新链表和原链表的连接即可。

        深拷贝原链表

        拷贝过后

        给random指针赋值

        断开新链表和原链表之前的连接

这样就深拷贝了原链表，返回新链表的头节点即可。

typedef struct Node Node;
// 创建节点
Node* BuyNode(int x) {Node* newnode = (Node*)malloc(sizeof(Node));newnode->next = newnode->random = NULL;newnode->val = x;return newnode;
}
// 深拷贝
void CopyList(Node** head) {Node* ptail = *head;Node* next = NULL;while (ptail) {next = ptail->next;Node* newnode = BuyNode(ptail->val);newnode->next = next;ptail->next = newnode;ptail = next;}
}
void Connect(Node** head) {Node* ptail = *head;Node* copy = (*head)->next;while (ptail) {copy = ptail->next;if (ptail->random)copy->random = ptail->random->next;ptail = copy->next;}
}
struct Node* copyRandomList(struct Node* head) {if (head == NULL){return NULL;} // 深拷贝原链表CopyList(&head);// 连接random指针Connect(&head);// 断开链表Node* ptail = head;Node* newhead = head->next;Node* copy = head->next;while (ptail->next->next) {ptail=copy->next;copy->next = copy->next->next;copy = copy->next;}return newhead;
}