链表(2) 链表面试题 C语言实现 数据结构 删除所有相同的值 链表反转 返回中间结点 返回倒数第k个结点 合并两个有序链表 链表划分 判断链表是否为回文结构 判断链表是否相交 判断链表中是否有环等等

3.4 链表面试题 第一题 删除链表中等于给定值 val 的所有结点并返回  新的头节点

struct ListNode* removeElements(struct ListNode* head, int val){
        struct ListNode*pre=NULL;
        struct ListNode*p=head;
        while(p!=NULL)
        {
            if(p->val==val)
            {
                if(p==head)
                {
                    head=head->next;
                    p=head;
                }
                else
                {
                   pre->next=p->next;
                   p=p->next;
                }
            }
            else
            {
                 pre=p;
                 p=p->next;
            }
        }
        return head;
}

第二题 

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

 方法一：头插

struct ListNode* reverseList(struct ListNode* head){
     struct ListNode*p=head;
     struct ListNode*newhead=NULL;
     while(p!=NULL)
     {
         struct ListNode*q=p->next;
         p->next=newhead;
         newhead=p;
         p=q;
     }
     return newhead;
}

方法2：三指针

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)return NULL;
     struct ListNode*n1=NULL;
     struct ListNode*n2=head;
     struct ListNode*n3=head->next;
     while(n2!=NULL)
     {
         n2->next=n1;
         n1=n2;
         n2=n3;
         if(n3!=NULL)
         n3=n3->next;
     }
     return n1;
}

第三题

给定一个头结点为 head 的非空单链表，返回链表的中间结点,如果有两个中间结点，则返回第二个中间结点

快慢指针 

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

第四题 输入一个链表，输出该链表中倒数第 k 个结点

快慢指针，快指针先走k步，快慢指针一起往后，当快指针为空时，慢指针指向倒数第k个,注意k的取值，k取值不合法时返回空指针

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    if(k<=0)return NULL;
    struct ListNode*fast=pListHead;
    struct ListNode*slow=pListHead;
    while(k)
    {
        if(fast==NULL)
            return NULL;
        fast=fast->next;
        k--;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

第五题 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有 结点组成的 归并，从头比较，取小的尾插到新链表

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
     if(list1==NULL)return list2;
     if(list2==NULL)return list1;
     struct ListNode*head=NULL;
     struct ListNode*tail=NULL;
     while(list1&&list2)
     {
         if(list1->valval)
         {
              if(tail==NULL)
              {
                  head=list1;
                  tail=list1;
              }
              else
              {
                  tail->next=list1;
                  tail=tail->next;
              }
              list1=list1->next;
         }
         else
         {
              if(tail==NULL)
              {
                  head=list2;
                  tail=list2;
              }
              else
              {
                  tail->next=list2;
                  tail=tail->next;
              }
              list2=list2->next;
         }
     }
     if(list1==NULL)tail->next=list2;
     else tail->next=list1;
     return head;
}

 第六题  以给定值 x 为基准将链表分割成两部分，所有小于 x 的结点排在大于或等于 x 的结点之前

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        if(pHead==NULL||pHead->next==NULL)return pHead;
        ListNode*pre=(ListNode*)malloc(sizeof(ListNode));
        ListNode*newhead=(ListNode*)malloc(sizeof(ListNode));
        pre->next=pHead;
        pHead=pre;
        newhead->next=NULL;
        ListNode*p=pre->next;
        ListNode*s=newhead;
        while(p!=NULL)
        {
            if(p->val>=x)
            {
                pre->next=p->next;
                p->next=NULL;
                s->next=p;
                s=s->next;
                p=pre->next;
            }
            else
            {
                p=p->next;
                pre=pre->next;
            }       
        }
            pre->next=newhead->next;
            pre=pHead;
            pHead=pHead->next;
            free(pre);
            pre=NULL;
            free(newhead);
            newhead=NULL;
        return pHead;
    }
};

搞一个新链表，把大于x的值尾插到新链表，再将两个链表连在一起

第七题

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构，给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构

class PalindromeList {
public:
    struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)return NULL;
     struct ListNode*n1=NULL;
     struct ListNode*n2=head;
     struct ListNode*n3=head->next;
     while(n2!=NULL)
     {
         n2->next=n1;
         n1=n2;
         n2=n3;
         if(n3!=NULL)
         n3=n3->next;
     }
     return n1;
}
    struct ListNode* middleNode(struct ListNode* head){
     struct ListNode*slow=head;
     struct ListNode*fast=head;
     while(fast!=NULL&&fast->next!=NULL)
     {
         fast=fast->next->next;
         slow=slow->next;
     }
     return slow;
}
    bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode*p=middleNode(A);
        ListNode*rhead=reverseList(p);
        ListNode*head=A;
        while(head!=NULL&&rhead!=NULL)
        {
            if(head->val!=rhead->val)
            {
                return false;
            }
            else
            {
                head=head->next;
                rhead=rhead->next;
            }
        }
        return true;       
    }
};

 找到中间结点，将中间结点及以后结点逆置，两个指针分别从头和中间结点向后两两比较

第八题

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点，如果两个链表不存在相交节点，返回 null

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL||headB==NULL)
    return NULL;
    int i=0,j=0;
    struct ListNode*pa=headA;
    struct ListNode*pb=headB;
    while(pa!=NULL)
    {
        pa=pa->next;
        i++;
    }
     while(pb!=NULL)
    {
        pb=pb->next;
        j++;
    }
    pa=headA;
    pb=headB;
    while(i>j)
    {
        pa=pa->next;
        i--;
    }
    while(j>i)
    {
        pb=pb->next;
        j--;
    }
    while(pa!=NULL&&pb!=NULL&&pa!=pb)
    {
        pa=pa->next;
        pb=pb->next;
    }
    return pa;
}

分别计算出两个链表的长度，指向长度大的指针向前走直到剩余结点和短的链表长度相同，再一起向前走，直到一个链表为空或遇到相交结点

第九题 给定一个链表，判断链表中是否有环

bool hasCycle(struct ListNode *head) {
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast!=NULL&&fast->next!=NULL)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        return true;
    }
    return false;
}

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行， 如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾 为什么快指针每次走两步，慢指针走一步一定可以追上？ 假设slow进环以后，fast跟slow的距离是N 这时fast真正开始追击slow，fast一次走两步，slow一次走一步，他们之间的距离每次缩小1，当N减到0时就相遇了 快指针一次走3步，走4步，...n步行吗？ 不一定能追上 第十题 给定一个链表，返回链表开始入环的第一个结点，如果链表无环，则返回 NULL

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

结论(别证了背下来算了): 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环 运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇