链表OJ题

文章目录

1. 链表的回文结构

因为单链表不能从后往前找节点，所以我们先找到中间节点，然后逆置，最后进行比较。

#include<stdio.h>#include<stdbool.h>typedefstructListNode{int val;structListNode* next;}ListNode;structListNode*middleNode(structListNode* head){
    ListNode* slow,* fast;
    slow = fast = head;while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;}return slow;}structListNode*reverseList(structListNode* head){if(NULL== head){return head;}
    ListNode* n1,* n2,* n3;
    n1 =NULL, n2 = head, n3 = head->next;while(n2){
        n2->next = n1;
        n1 = n2;
        n2 = n3;if(n3){
            n3 = n3->next;}}return n1;}
bool chkPalindrome(ListNode* A){
    ListNode* mid =middleNode(A);
    ListNode* rmid =reverseList(mid);while(A && rmid){if(A->val != rmid->val){return false;}
        A = A->next;
        rmid = rmid->next;}return true;}

2. 相交链表

#include<stdio.h>#include<stdlib.h>structListNode{int val;structListNode* next;};structListNode*getIntersectionNode(structListNode* headA,structListNode* headB){structListNode* curA = headA;structListNode* curB = headB;int lenA =0;while(curA->next){++lenA;
        curA = curA->next;}int lenB =0;while(curB->next){++lenB;
        curB = curB->next;}//不相交if(curA != curB){returnNULL;}int gap =abs(lenA - lenB);//因为我们不知道A长还是B长，所以我们要用假设法，先假设A长，如果不对，再调换一下就行structListNode* longList = headA;structListNode* shortList = headB;if(lenB > lenA){
        longList = headB;
        shortList = headA;}//让长的先走gap步while(gap--){
        longList = longList->next;}//再同时走，找交点while(longList != shortList){
        longList = longList->next;
        shortList = shortList->next;}return longList;}

3. 链表中倒数第k个结点

思路2：

#include<stdio.h>structListNode{int val;structListNoe* next;};structListNode*FindKthToTail(structListNode* pListHead,int k){structListNode* slow = pListHead,* fast = pListHead;//fast先走k步while(k--){//k还没有减到0，链表已经空了，说明k大于链表的长度if(NULL== fast){returnNULL;}
        fast = fast->next;}//slow和fast同时走，fast走到空，slow就是倒数第k个while(fast){
        slow = slow->next;
        fast = fast->next;}return slow;}

4. 环形链表

#include<stdbool.h>structListNode{int val;structListNode* next;};
 
bool hasCycle(structListNode* head){structListNode* slow = head,* fast = head;while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;if(slow == fast){return true;}}return false;}

5. 环形链表 II

找入环点：

法一：

#include<stdio.h>structListNode{int val;structListNode* next;};structListNode*detectCycle(structListNode* head){structListNode* slow = head,* fast = head;while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;if(slow == fast){structListNode* meet = slow;while(meet != head){
                meet = meet->next;
                head = head->next;}return meet;}}returnNULL;}

法二：

#include<stdio.h>#include<stdlib.h>structListNode{int val;structListNode* next;};structListNode*getIntersectionNode(structListNode* headA,structListNode* headB){structListNode* curA = headA;structListNode* curB = headB;int lenA =0;while(curA->next){++lenA;
        curA = curA->next;}int lenB =0;while(curB->next){++lenB;
        curB = curB->next;}//不相交if(curA != curB){returnNULL;}int gap =abs(lenA - lenB);structListNode* longList = headA;structListNode* shortList = headB;if(lenB > lenA){
        longList = headB;
        shortList = headA;}//让长的先走gap步while(gap--){
        longList = longList->next;}//再同时走，找交点while(longList != shortList){
        longList = longList->next;
        shortList = shortList->next;}return longList;}structListNode*detectCycle(structListNode* head){structListNode* slow = head,* fast = head;while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;if(slow == fast){structListNode* meet = slow;structListNode* headx = meet->next;
            meet->next =NULL;returngetIntersectionNode(head, headx);}}returnNULL;}

6. 随机链表的复制

写代码的时候建议一边画细图，一边写：

#include<stdio.h>#include<stdlib.h>structNode{int val;structNode*next;structNode*random;};structNode*copyRandomList(structNode* head){structNode* cur = head;//拷贝节点插入原节点的后面while(cur){structNode* copy =(structNode*)malloc(sizeof(structNode));
        copy->val = cur->val;//插入
        copy->next = cur->next;
        cur->next = copy;//迭代
        cur = cur->next->next;}//控制拷贝节点的random
    cur = head;while(cur){structNode* copy = cur->next;if(NULL== cur->random){
            copy->random =NULL;}else{
            copy->random = cur->random->next;}//迭代
        cur = cur->next->next;}//把copy节点解下来，链接成新链表structNode* copyhead =NULL,* tail =NULL;
    cur = head;while(cur){structNode* copy = cur->next;structNode* next = copy->next;//尾插if(NULL== tail){
            copyhead = tail = copy;}else{
            tail->next = copy;
            tail = tail->next;}
        cur->next = next;
        cur = next;}return copyhead;}