链表算法练习

练习1：移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

思路： 创建新链表，并且建立头尾指针，将原链表不等于val的值尾插到新链表中。

typedef struct ListNode LN;
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    LN* newhead,*newtile;
    newhead=newtile=NULL;
    LN* pcur=head;
    while(pcur)
    {
        if(pcur->val!=val)
        {
            if(newhead==NULL)
            {
                newhead=newtile=pcur;
            }
            else
            {
                newtile->next=pcur;
                newtile=newtile->next;
            }
        }
        pcur=pcur->next;
    }
    if(newtile!=0)
        newtile->next=NULL;
    return newhead;
}

注意：在写代码中，最后一定要判断nwetile是否等于零，从而使下一个指针指向NULL，否则就会出现下面的错误，导致最后面与val相同的值没有删除。

if(newtile!=0)
    newtile->next=NULL;

练习2：反转链表

206. 反转链表 - 力扣（LeetCode）

思路：创建三个指针，就能在原链表上修改指针指向。

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

练习3：链表的中间结点

876. 链表的中间结点 - 力扣（LeetCode）

思路：快慢指针，慢指针每次走一次，快指针则每次走两次。

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

练习4：返回倒数第k个节点

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

思路：采用两次遍历，先求出链表一共有几个数，再进行返回。

typedef struct ListNode LN;
int kthToLast(struct ListNode* head, int k) {
    LN* pcur=head;
    int n=0;
    while(pcur)
    {
        pcur=pcur->next;
        n++;
    }
    pcur=head;
    while(n-k)
    {
        pcur=pcur->next;
        k++;
    }
    return pcur->val;
}

练习5：合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

思路：创建新链表，遍历原链表，比较大小，谁小尾插到新链表后面

typedef struct ListNode LN;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    if(list1==NULL)
    {
        return list2;
    }
    else if(list2==NULL)
    {
        return list1;
    }

    LN* newhead,*newtile;
    newhead=newtile=(LN*)malloc(sizeof(LN));

    while(list1 && list2)
    {
        if(list1->val < list2->val)
        {
            newtile->next=list1;
            newtile=newtile->next;
            list1=list1->next;
        }
        else
        {
            newtile->next=list2;
            newtile=newtile->next;
            list2=list2->next;
        }
    }

    if(list1!=0)
    {
        newtile->next=list1;
    }
    else
    {
        newtile->next=list2;
    }

    LN *ret=newhead->next;
    free(newhead);
    newhead=NULL;
    return ret;
}

练习6：链表分割

链表分割_牛客题霸_牛客网

思路：创建两个链表的头尾结点，对链表分别进行小的和大的的尾差，连接两个链表。

class Partition 
{
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        // write code here
        ListNode* phead,*ptile;
        phead=ptile=(ListNode*)malloc(sizeof(ListNode));

        ListNode* ghead,*gtile;
        ghead=gtile=(ListNode*)malloc(sizeof(ListNode));

        ListNode* pcur=pHead;
        while(pcur)
        {
            if(pcur->val < x)
            {
                ptile->next=pcur;
                ptile=ptile->next;
                pcur=pcur->next;
            } 
            else
            {
                gtile->next=pcur;
                gtile=gtile->next;
                pcur=pcur->next;
            } 
        }

        gtile->next=NULL;
        ptile->next=ghead->next;
        ListNode* ret=phead->next;
        free(ghead);
        free(phead);
        ghead=phead=NULL;
        return ret;
    }
};

练习7：链表的回文结构

链表的回文结构_牛客题霸_牛客网

思路：先找到中间结点，然后对后半部分进行反转，比较前半部分和反转后的后半部分。

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode* show=A;
        ListNode* fast=A;
        while(fast && fast->next)
        {
            show=show->next;
            fast=fast->next->next;
        } 

        ListNode* n1,*n2,*n3;
        n1=NULL;
        n2=show;
        n3=n2->next;
        while(n2)
        {
            n2->next=n1;
            n1=n2;
            n2=n3;
            if(n3)
                n3=n3->next;
        }
        ListNode* right=n1;

        ListNode* left=A;

        while(right)
        {
            if(right->val != left->val)
                return false;
            right=right->next;
            left=left->next;
        }
        return true;
    }
};

练习8：相交链表

160. 相交链表 - 力扣（LeetCode）

思路：找两个链表结点数的相差值，长链表先走相差的数，然后两个开始遍历，找是否有相交的点。

typedef struct ListNode LN;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    LN* l1=headA;
    LN* l2=headB;
    int size1=0,size2=0;
    while(l1)
    {
        size1++;
        l1=l1->next;
    }
    while(l2)
    {
        size2++;
        l2=l2->next;
    }
    int get=abs(size1-size2);

    LN* llong=headA;
    LN* sshort=headB;
    if(size1 < size2)
    {
        llong=headB;
        sshort=headA;
    }

    while(get)
    {
        llong = llong->next;
        get--;
    }

    while(llong && sshort)
    {
        if(sshort==llong)
        {
            return llong;
        }
        llong=llong->next;
        sshort=sshort->next;
    }
    return NULL;
}

练习9：环形链表（1）

141. 环形链表 - 力扣（LeetCode） 

思路：使用快慢指针。

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

练习10：环形链表（2）

142. 环形链表 II - 力扣（LeetCode）

思路：快慢指针，找到相遇点后，从头结点和相遇结点分别开始遍历，如果两个中间相遇则找到索引的链表结点。

typedef struct ListNode LN;
struct ListNode *detectCycle(struct ListNode *head) {
    LN* slow=head;
    LN* fast=head;

    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {
            LN* pcur=head;
            while(pcur!=fast)
            {
                pcur=pcur->next;
                fast=fast->next;
            }
            return pcur;
        }
    }
    return false;
}

练习11：随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

思路：在原来链表基础上，每个结点后面加入新的结点，并且进行一比一复制，然后使复制链表与原链表断开。

typedef struct Node node;
struct Node* copyRandomList(struct Node* head) {
	if(head==NULL)
    {
        return NULL;
    }

    node* pcur=head;
    while(pcur)
    {
        node* next=pcur->next;
        node* newnode=(node*)malloc(sizeof(node));
        newnode->val=pcur->val;
        newnode->next=newnode->random=NULL;

        pcur->next=newnode;
        newnode->next=next;

        pcur=next;
    }

    pcur=head;
    while(pcur)
    {
        node* copy=pcur->next;
        if(pcur->random!=NULL)
        {
            copy->random=pcur->random->next;
        }
        pcur=copy->next;
    }

    pcur=head;
    node* phead,*ptile;
    phead=ptile=pcur->next;
    while(pcur->next->next)
    {
        pcur=pcur->next->next;
        ptile->next=pcur->next;
        ptile=ptile->next;
    }
    return phead;
}