链表OJ练习（2）

一、分割链表

题目介绍：

思路：创建两个链表，ghead尾插大于x的节点，lhead尾插小于x的节点。先遍历链表。最后将ghead尾插到lhead后面，将大小链表链接。

      我们需要在创建两个链表指针，指向两个链表的头节点，用这两个指针标记lhead和ghead的尾结点，方便与尾插。

注：极端边界场景：所有值都小于x; 所有值都大于x; 空链表。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x)
    {
        ListNode* gtail, * ghead, * ltail, * lhead;
        gtail = ghead = (struct ListNode*)malloc(sizeof(struct ListNode));
        ltail = lhead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                ltail->next = cur;
                ltail = ltail->next;
            }
            else
            {
                gtail->next = cur;
                gtail = gtail->next;
            }
            cur = cur->next;
        }
        ltail->next = ghead->next;
        gtail->next = NULL;
        struct ListNode* newhead = lhead->next;
        free(lhead);
        free(ghead);
        return newhead;
    }
};

二、回文链表

题目介绍：

思路：先找到中间节点，可以利用快慢指针找到中间节点，然后将中间节点后面的节点翻转，在和中间节点前面的链表依次比较，如果全部相同则是回文链表否则不是。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* falst;
    struct ListNode* slow;
    falst = head;
    slow = head;
    while (falst && falst->next)
    {
        slow = slow->next;
        falst = falst->next->next;
    }
    return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while (cur)
    {
        struct ListNode* next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;

        cur = next;
    }
    return newhead;
}

class PalindromeList
{
public:
    bool chkPalindrome(ListNode* head)
    {
        //找到中间节点，将中间节点后面的链表翻转，有第一个和中间节点比较，并依次后移，若全部相同，则为回文链表，反之不是。
        struct ListNode* mid = middleNode(head);
        struct ListNode* rmid = reverseList(mid);
        while (rmid && mid)
        {
            if (rmid->val != head->val)
            {
                return false;
            }
            head = head->next;
            rmid = rmid->next;
        }
        return true;
    }

};

三、找公共点

题目介绍：

思路：先遍历两个链表，计算出两个链表的长度，让后计算出两个链表的长度差k，将长的链表先往前走k步，然后将两个链表指针同时后移，找到第一个相同的节点就是相交节点。

注：需要考虑到空链表，给链表判空，若空headA和headB其中一个为空返回NULL。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
   struct ListNode* curA = headA;
   struct ListNode* curB = headB;
   int lenA = 1;
   int lenB = 1;
   if(headA==NULL||headB==NULL)
   {
       return NULL;
   }
   while (curA->next)
   {
       curA = curA->next;
       lenA++;
   }
   while (curB->next)
   {
       curB = curB->next;
       lenB++;
   }
   if (curA != curB)  //没有交点
   {
       return false;
   }
   int gap = abs(lenA - lenB);
   struct ListNode* falst = headA;
   struct ListNode* slow = headB;
   if (lenA < lenB)
   {
       falst = headB;
       slow = headA;
   }
   while (gap--)
   {
       falst = falst->next;
   }
   while (slow != falst)
   {
       slow = slow->next;
       falst = falst->next;
   }
   return slow;
}

四、判断是否是环形链表

题目介绍：

思路：还是利用快慢指针，当慢指针往前走一步，快指针往前走两步，在一个环中，每次他们的距离就减少一，如果有环，就一定能追上。如果没追上则没有环。

用快指针遍历。

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

    }
    return false;
}

五、寻找环形链表的入环节点

题目描述：

思路1：假设链表带环，头节点head与入环节点的距离为L，入环节点与相遇点的距离为D，环的大小为C，如下图：

fast从头节点到相遇点：L + D + kC，其中k为正整数，表示在快慢指针相遇前fast所走圈数

slow从头节点到相遇点：L + D

又由于fast每次走两步，slow每次走一步，以上二式可以建立起联系：

L + D + kC = 2 * (L + D)

L = kC - D = (k - 1) * C + C - D

所以可以得出结论：一个指针从相遇点开始走，一个指针从链表头开始走，则这两个指针一定会在入环节点处相遇。

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast=head, *slow=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            //找相遇点meetNode
            struct ListNode* meetNode = fast;
            //相遇点可能就是入环节点
            if(meetNode == head)
                return head;
            //meetNode和head开始每次走一步，直到相遇
            while(head && meetNode)
            {
                meetNode = meetNode->next;
                head = head->next;
                //当相遇时即为入环节点
                if(meetNode == head)
                   return meetNode;
            }
        }
    }
    return NULL;
}

思路2：我们可以在相遇点将链表断开，找到如节点就相当于找到两个链表的交点。

找两个链表的交点我们可以参考题目三

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode *curA=headA;
    struct ListNode *curB=headB;
    int lenA=1;
    int lenB=1;
    while(curA->next)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB=curB->next;
        lenB++;
    }
    if(curA!=curB)  //没有交点
    {
        return false;
    }
    int gap=abs(lenA-lenB);
    struct ListNode *falst=headA;
    struct ListNode *slow=headB;
    if(lenA<lenB)
    {
        falst=headB;
        slow=headA;
    }
    while(gap--)
    {
        falst=falst->next;
    }
    while(slow!=falst)
    {
        slow=slow->next;
        falst=falst->next;
    }
    return slow;
}
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)  //相遇了
        {
            struct ListNode *meet=slow;  //将环断开
            struct ListNode *newhead=meet->next;
            meet->next=NULL;
            return getIntersectionNode(head,newhead); //找两个链表的交点
        }
    }
    return NULL;
}