【链表】算法题（二） ----- 力扣/牛客
一、链表的回文结构
思路：
找到链表的中间节点，然后逆置链表的后半部分，再一一遍历链表的前半部分和后半部分，判断是是否为回文结构。
快慢指针找到链表的中间节点
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; }