链表Oj练习题 纯C语言

目录

链表分割

链表的回文结构

相交链表

环形链表

环形链表 II

---

链表分割

链表分割

 思路：

1. 遍历原链表
2. 把<x的插入到一个链表
3. 把>=×的插入到一个链表
4. 链表1和链表2链接起来

假设链表为3 5 1 6 3 4

则分为： 3 1 3       5 6 4

之后相连即可

魔鬼细节：如图所示，如果6是大链的最后一个数，那么greaterTail->next仍然指向3，会成环

所以需要greaterTail->next=NULL;  防止死循环

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode*lessHead,*lessTail,*greaterHead,*greaterTail;
        lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        
        lessTail->next=greaterTail->next=NULL;
        
        struct ListNode* cur=pHead;
        while(cur){
            if(cur->val<x)
            {
                lessTail->next=cur;
                lessTail=lessTail->next;
            }
            else
            {
                greaterTail->next=cur;
                greaterTail=greaterTail->next;
            }
            cur=cur->next;
        }
        
        lessTail->next=greaterHead->next;
        greaterTail->next=NULL;    //致命细节
        
        struct ListNode* list=lessHead->next;
        return list;

            
    }
};

链表的回文结构

链表的回文结构

 思路：用快慢指针找到中间节点，再用链表反转反转中间节点后的链表，将链表和反转的链表一一对比即可

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    
    struct ListNode* middleNode(struct ListNode*head)
    {
        struct ListNode*slow,*fast;
        slow=fast=head;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next;
        }
         return slow;
    }
    
    struct ListNode*reverse(struct ListNode*head)
    {
        struct ListNode*newHead=NULL;
        struct ListNode*cur=head;
        while(cur)
        {
            struct ListNode*next=cur->next;
            cur->next=newHead;
            newHead=cur;
            cur=next;
        }
        return newHead;
    }

    bool chkPalindrome(ListNode* A)
    {
        struct ListNode* mid=middleNode(A);    //快慢指针
        struct ListNode* rHead=reverse(mid);    //链表反转
        
        while(A&&rHead)   
        {
            if(A->val==rHead->val) //一一对比
            {
                A=A->next;
                rHead=rHead->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};

相交链表

相交链表

思路：（让两链表长度相等）算出链A与链B的长度并相减得到相差长度，用长链表减去相差长度；将链表指针一一对比即可

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA=headA,*tailB=headB;
    int lenA=1,lenB=1;
    while(tailA->next)
    {
        tailA=tailA->next;
        lenA++;
    }
    while(tailB->next)
    {
        tailB=tailB->next;
        lenB++;
    }

    if(tailA!=tailB)
    {
        return NULL;    //若尾链都不相等，则不相交
    }

    struct ListNode*shortList=headA,*longList=headB;
    if(lenA>lenB)
    {
        longList=headA;
        shortList=headB;
    }
    int x=abs(lenB-lenA);
    while(x--)
    {
        longList=longList->next;
    }
    while(shortList&&longList)
    {
        if(shortList==longList)
            return shortList;

        shortList=shortList->next;
        longList=longList->next;
    }
    return NULL;

}

环形链表

环形链表 II

 思路：用快慢指针，为了保证一定能追到并相遇，快指针与漫指针的差为1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode*slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
            return true;
    }
    return false;

}

环形链表 II

环形链表 II

思路：数学证明

• L很小,C很大，slow进环前，fast可能在环里面，一圈都没走完
• L很大,C很小，slow进环前，fast在环里面走了很多圈了
• 但是slow进环以后，在一圈之内，fast一定追上slow因为slow进环以后，他们之间距离最多是C-1
   

设从头节点到环的入口点的步数为L，环的长度为C。

假设环入口点走X步快慢指针相遇了。

可得出：

慢指针走的路程为：L+X。

快指针走的路程为：L+X+C*N（其中N代表圈数，N>=1）。

快指针路程是慢指针路程的两倍

所以：L+X+C*N=2*(L+X)。

化简得：L=C*N-X

                L=C*(N-1)+C-X。

因此我们只需要让一个指针从head走，另一个指针从meet走，当两指针相等时，它们就指向环的入口点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        {
            struct ListNode*meet=slow;
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL;
}