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

一、链表的回文结构思路找到链表的中间节点然后逆置链表的后半部分再一一遍历链表的前半部分和后半部分判断是是否为回文结构。快慢指针找到链表的中间节点slow指针指向的就是中间节点逆置链表后半部分逆置链表后半部分遍历链表前半部分和后半部分如果left和right指向的数据不相等就跳出循环返回false如果遍历到left或者right为NULL数据都相等那么链表具有回文结构返回true。这里如果是奇数个节点遍历结束后class PalindromeList { public: //找链表中间节点 ListNode* Listmid(ListNode* phead) { ListNode* fast, *slow; fastslowphead; while(fast fast-next) { slowslow-next; fastfast-next; } return slow; } //逆置 ListNode* reverse(ListNode* phead) { ListNode* l1,*l2,*l3; l1NULL; l2phead; while(l2) { l3l2-next; l2-nextl1; l1l2; l2l3; } return l1; } bool chkPalindrome(ListNode* A) { // write code here //找到链表中间节点 ListNode* midListmid(A); //逆置后半部分 ListNode* phead reverse(mid); //比较 ListNode* left, *right; leftA; rightphead; while(right left) { if(right-val!left-val) { return false; } leftleft-next; rightright-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 slowfast向前走两步slow向前走一步fast向前走两步slow向前走一步fast向前走两步slow向前走一步此时fast和slow相遇证明链表中存在环返回true。如果链表不存在环结构遍历过程中fast或者fast-next指针会等于NULL将这个作为结束条件即可。typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) { ListNode* fast, *slow; fastslowhead; while(fast fast-next) { fastfast-next-next; slowslow-next; if(slow fast) { return true; } } return false; }四、环形链表2上面只是让我们判断链表是否带环这道题让我们返回链表环的起始节点如果不存在环就返回NULL。思路使用快慢指针找到快慢指针的相遇节点再定义两个指针从相遇节点和链表头结点开始遍历两个指针相遇时的节点就是链表环的起始节点。根据题目的示例来分析先找到链表快慢指针的相遇节点定义两个指针从链表头部和相遇节点开始遍历链表遍历链表直到两个指针相遇两个指针相遇此时指针指向的节点就是链表环的起始节点。typedef struct ListNode ListNode; ListNode* hasCycle(struct ListNode *head) { ListNode* fast, *slow; fastslowhead; while(fast fast-next) { fastfast-next-next; slowslow-next; if(slow fast) { return slow; } } return NULL; } struct ListNode *detectCycle(struct ListNode *head) { //找到快慢指针相遇节点 ListNode* poshasCycle(head); if(posNULL) { return NULL; } //从头结点和相遇节点开始遍历 ListNode* ptailhead; while(1) { if(posptail) { return pos; } pospos-next; ptailptail-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) { ptailcopy-next; copy-next copy-next-next; copy copy-next; } return newhead; }