【数据结构】单链表(长期维护)（2）

struct ListNode* middleNode(struct ListNode* head) {
    //思路1：暴力求解法
    /*int length = 0;
    struct ListNode* pcur = head;
    while(pcur)
    {
        length++;
        pcur = pcur->next;
    }
    length/=2;
    pcur = head;
    while(length--)
    {
        pcur = pcur->next;
    }
    return pcur;
    */
    //思路2：双指针法
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 struct ListNode* removeElements(struct ListNode* head, int val){
    
    //处理*head == val 的情况，使*head！=val
    while (head && head->val == val) 
    {
        head = head->next;
    }
    //如果是空链表，返回
    if(head == NULL)
    {
        return NULL;
    }
    
    //走到这里，head不是val并且该链表不为空
    struct ListNode* cur = head->next;//如果head为空链表这样写不合法
    struct ListNode* pre = head;
    while (cur != NULL) {
        if (cur->val == val) 
        {
        //跳跃
        pre->next = cur->next;
        //free
        struct ListNode* temp = cur;
        } 
        else 
        {
            //下一个跟进cur
            pre = cur;
        }
        //cur不断向前走
        cur = cur->next;
    }
    return head;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 struct ListNode* removeElements(struct ListNode* head, int val){
    
    //定义新链表的头尾指针
    struct ListNode* newHead = NULL;
    struct ListNode* newTail = NULL;
    //
    struct ListNode* pcur = head;
    while(pcur)
    {
        //不是val，尾插到新链表
        if(pcur->val!=val)
        {
            if(newHead == NULL)
            {
                //链表为空
                newHead = newTail = pcur;
            }
            else//链表不为空
            {
                newTail->next = pcur;
                newTail = newTail->next;//更新尾节点
            }
        }
        //更新pcur指针
        pcur = pcur->next;
    }
    //加上null
        if(newTail)
        {
            newTail->next = NULL;
        }
    //返回
        return newHead;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    //防止给我一个空的链表,如果说给我一个空链表，那么我们下面的n2->next会报错
    if(head == NULL) 
    return head;
    
    //指针初始化
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = n2->next;
     
    while(n2)
    {
        n2->next = n1;//改变指向
        n1 = n2;
        n2 = n3;
        if(n3)//如果n3不为空，那么让n3往下走一个
        n3 = n3->next;
    }
    return n1;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    //头插的思路
struct ListNode* newhead = NULL;
struct ListNode* pcur = head;
while(pcur)
{
    struct ListNode* next = pcur->next;
    pcur->next = newhead;
    newhead = pcur;
    pcur = next;
}
    
return newhead;
}

#include<stdio.h>
#include<stdlib.h>
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        //申请哨兵位置
        struct ListNode* sentry1 = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* sentry2 = (struct ListNode*)malloc(sizeof(struct ListNode));
        //定义指针
        struct ListNode* newhead1,*newhead2,*newtail1,*newtail2;
        newhead1 = newtail1 = sentry1;
        newhead2 = newtail2 = sentry2;
        //按照条件分割
        struct ListNode* pcur = pHead;
        while(pcur)
        {
            if(pcur->val<x)
            {
                newtail1->next = pcur;
                newtail1 = newtail1->next;
            }
            else 
            {
                newtail2->next = pcur;
                newtail2 = newtail2->next;
            }
            pcur = pcur->next;
        }
        //链接list1与list2
        
        newtail1->next = newhead2->next;
        newtail2->next = NULL;
        pHead = newhead1->next;
        free(newhead1);
        free(newhead2);
        return pHead;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int kthToLast(struct ListNode* head, int k){
struct ListNode* pcur = head;
int count = 0;
while(pcur)
{
    count++;
    pcur = pcur->next;
}
count = count - k;
pcur = head;
while(count--)
{
    pcur = pcur->next;
}
return pcur->val;
}

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //考虑空链表的情况：
    //1.两个链表都是空的
    if(list1 == NULL && list2 == NULL)
    {
        return NULL;
    }
    //2.只有list1是空的
    if(list1 == NULL)
    {
        return list2;
    }
    //3.只有list2是空的
    if(list2 == NULL)
    {
        return list1;
    }
    //走到这里，就说明两个链表都不为空了。
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    //定义两个指针分别遍历两个链表
    struct ListNode* pcur1 = list1;
    struct ListNode* pcur2 = list2;
    while(pcur1 && pcur2)
    {
        if(pcur1->val < pcur2->val)
        {
            if(head == NULL)
            {
                head = tail = pcur1;
            }
            else
            {
                tail->next = pcur1;
                tail = pcur1;
            }
            pcur1 = pcur1->next;
        }
        else
        {
            if(head == NULL)
            {
                head = tail = pcur2;
            }
            else
            {
                tail->next = pcur2;
                tail = pcur2;
            }
            pcur2 = pcur2->next;
        }
    }
    //走到这里，会出现两种情况，要不剩下list1，要不剩下list2
    while(pcur1)
    {
        tail->next = pcur1;
        tail = pcur1;
        pcur1 = pcur1->next;
    }
    while(pcur2)
    {
        tail->next = pcur2;
        tail = pcur2;
        pcur2 = pcur2->next;
    }
    return head;
}

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//找到中间结点
struct ListNode* middleNode(struct ListNode* head) {
    //思路2：快慢指针法
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)//快指针走到头
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
    //逆置链表为空
    if(head == nullptr) 
    return head;
    //不为空
    struct ListNode* n1 = nullptr;
    struct ListNode* n2 = head;
    struct ListNode* n3 = head->next;
    while(n2)
    {
        //逆置
        n2->next = n1;
        //移动n1、n2、n3指向下一个
        n1 = n2;
        n2 = n3;
        if(n3)//n3不为空
        {
            n3 = n3->next;
        }
    }
    return n1;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        //找到中间节点
        struct ListNode* pMidNode = middleNode(A);
        //逆置中间节点及其以后的节点
        struct ListNode* pNewMidNode = reverseList(pMidNode);
        //对比
        while(A&&pNewMidNode)
        {
            if(pNewMidNode->val!=A->val)
            {
                return false;
            }
            //向后走
            A = A->next;
            pNewMidNode = pNewMidNode->next;
        }
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 #include<math.h>
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    //判断是不是相交链表
    struct ListNode* pTailA = headA;
    struct ListNode* pTailB = headB;
    int skipA = 0;//统计A链表中结点的个数
    int skipB = 0;//统计B链表中结点的个数
    //统计结点个数
    while(pTailA->next)
    {
        pTailA=pTailA->next;
        skipA++;
    }
    skipA++;//统计少了一个，给他加上
     while(pTailB->next)
    {
        pTailB=pTailB->next;
        skipB++;
    }
    skipB++;
    //不是交点
    if(pTailA!=pTailB)
    {
        return NULL;
    }
    //如果是，那么证明他们一定是相交的了，所以我们要查找出他的交点
    
    int sub = abs(skipA-skipB); 
    struct ListNode* pmin = NULL;
    struct ListNode* pmax = NULL;
    
    if(skipA<skipB)
    {
        pmin = headA;
        pmax = headB;
    }
    else
    {
        pmin = headB;
        pmax = headA;
    }
    //让长的先走一些，让长短对齐
    while(sub--)
    {
        pmax = pmax->next;
    }
    //找交点
    while(pmin!=pmax)
    {
        pmin = pmin->next;
        pmax = pmax->next;
    }
    
    return pmax;
}

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
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(fast == slow)
        {
            struct ListNode * meet = slow;
            struct ListNode * headx = head;
            while(meet!=headx)
            {
                meet = meet->next;
                headx = headx->next;
            }
            return meet;
        }
    }
    return NULL;
}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    //首先统计每个链表结点的个数
    int count1 = 0;
    int count2 = 0;
    struct ListNode *pcur1 = headA,*pcur2 = headB;
    while(pcur1)
    {
        count1++;
        pcur1 = pcur1->next;
    }
    while(pcur2)
    {
        count2++;
        pcur2 = pcur2->next;
    }
    struct ListNode *maxhead = headA;
    struct ListNode *minhead = headB;
    if(count1 < count2)
    {
        maxhead = headB;
        minhead = headA;
    }
    int sub = count1-count2;
    if(sub<0)
    {
        sub = 0-sub;
    }
    while(sub--)
    {
        maxhead = maxhead->next;
    }
    while(minhead!=maxhead)
    {
        minhead = minhead->next;
        maxhead = maxhead->next;
    }
    return maxhead;
}
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* head1 = slow->next;
        struct ListNode* head2 = head;
        slow->next = NULL;
        struct ListNode* meet = getIntersectionNode(head1,head2);
        return meet;
    }
   }
   return NULL;
}

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
struct Node* copyRandomList(struct Node* head) {
    if(head==NULL)
    {
        return NULL;
    }
  struct Node* pcur = head;
    //插入一些复制结点
    while(pcur)
    {
        struct Node* pushback = (struct Node*)malloc(sizeof(struct Node));
        pushback->val = pcur->val;
        pushback->next = pcur->next;
        pcur->next = pushback;
        pcur = pcur->next->next;//调整pcur
    }
    //控制拷贝结点的random
    pcur = head;
    while(pcur)
    {
        //如果原链表的random指向空，那我们新链表也要指向空
        if(pcur->random == NULL)
        {
            pcur->next->random = NULL;
            pcur = pcur->next->next;
            continue;
        }
        pcur->next->random = pcur->random->next;
        pcur = pcur->next->next;
    }
    //把拷贝结点放下来
    pcur = head;
    struct Node* pcurx = head->next;
    struct Node* returnpcurx = pcurx; 
    while(pcur)
    {
        pcur->next = pcur->next->next;
        pcur = pcur->next;
        //最后一个节点
        if(pcurx->next == NULL)
        {
            pcurx->next = NULL;
            break;
        }
        pcurx->next = pcurx->next->next;
        pcurx = pcurx->next;
    }
    //返回
    return returnpcurx;
}