leetcode刷题---链表

1.删除链表的倒数第N个节点

根据题目描述，第一个思路是存到数组中对数组进行操作，想到数组我们就可以想到下标和倒数第N个的关系，所以我们可以不额外开空间，可以直接遍历数组求出倒数第N个和链表size之间的关系，然后遍历数组，找到倒数第N个是正数第多少个就可以直接删除那个位置的节点，注意，我们还需要用一个结构体指针变量记录前一个位置。

代码展示：

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    int size=0;//链表大小
    struct ListNode*cur=head;//遍历链表需要的指针
    //求出链表大小
    while(cur)
    {
        cur=cur->next;
        size++;
    }
    //特殊处理：当删除的是最后一个节点的时候，直接删除最后一个位置的节点
    if(n==size)
    {
        struct ListNode*newhead=head->next;
        free(head);
        return newhead;
    }
    int i=size-(n-1);//找出i和size的关系
    struct ListNode*prev=NULL;
    cur=head;
    //遍历数组
    while(i!=1)
    {
        prev=cur;//记录前一个位置
        cur=cur->next;
        i--;
    }
    struct ListNode*next=cur->next;
    free(cur);
    prev->next=next;
    return head;
}

两两交换链表中的节点

分析题目：题目的要求是让我们交换节点，注意：不是交换节点的值，而是节点之间的交换，首先我们先讨论特殊情况，如果链表为空或者链表只有一个节点则不用交换直接返回头节点，一般情况：我们可以定义一个fast（快指针），然后前后交换了之后，fast走两步，直接就来到了下一个交换的位置，用tmp记录下下个节点的值，这样才能将链表前面的值串起来，==注意：有一种特殊情况，当链表的节点是奇数个的时候最后一个节点不需要交换，所以循环中的终止条件有两个一个是：fast!=NULL还有一个是fast->next，接下来完善代码即可。

代码展示

struct ListNode* swapPairs(struct ListNode* head) {
	//特殊情况处理
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    //定义fast指针
    struct ListNode*fast=head;
    while(fast!=NULL)
    {
        if(fast->next==NULL)//奇数情况讨论
        {
            break;
        }
        //交换前后节点
        int tmp=fast->val;
        fast->val=fast->next->val;
        fast->next->val=tmp;
        fast=fast->next->next;
    } 
    return head;
}

题目分析：将小于k的值放在链表左边，将大于或者等于k的值放在链表右边

思路:这里我们需要的6个变量，一个是小于k的链表的头EH，还有尾ET，一个是大于或等于k的头MH和尾MT，还有一个用于遍历链表的变量cur，还有一个变量就是记录cur的下一个位置的变量next，将除了cur以外的变量置为空，然后当遍历数组的时候访问每个节点的val，如果值小于k则用EH和ET连接，如果大于或者等于k的链表，则用MH和MT连接起来，最后将两个链表重新连接起来，最后返回头节点EH。
下图展示思路过程：
代码展示

struct ListNode* partition(struct ListNode* head, int x) {
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    //小于K的头和尾
    struct ListNode*EH=NULL;
    struct ListNode*ET=NULL;
    //大于或等于K的头和尾
    struct ListNode*MH=NULL;
    struct ListNode*MT=NULL;
    //遍历链表的变量和记录下一个节点的变量
    struct ListNode*cur=head;
    struct ListNode*next=NULL;
    while(cur)
    {
        next=cur->next;
        //判断之后连接
        if(cur->val<x)
        {
            if(EH==NULL&&ET==NULL)
            {
                EH=ET=cur;
                ET->next=NULL;
            }
            else
            {
                ET->next=cur;
                ET=cur;
                ET->next=NULL;
            }
        }
        else{
            if(MH==NULL&&MT==NULL)
            {
                MH=MT=cur;
                MT->next=NULL;
            }
            else{
                MT->next=cur;
                MT=cur;
                MT->next=NULL;
            }
        }
        cur=next;
    }
    //讨论当没有小于K的值的节点时返回大于或者等于K的链表的头
    if(EH==NULL)
    {
        return MH;
    }
    //返回链表头节点
    ET->next=MH;
    return EH;
}

反转链表2

思路:将链表left前面的节点封装成一个链表，将left和right中间的链表进行翻转，也就是头插，将right后面的节点封装成一个链表，然后将三个链表连接起来返回头结点，方法和上面的隔离链表类似

代码展示

struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    if(head->next==NULL||head==NULL)
    {
        return head;
    }
    struct ListNode*midH=NULL;
    struct ListNode*midT=NULL;
    struct ListNode*leftH=NULL;
    struct ListNode*leftT=NULL;
    struct ListNode*rightH=NULL;
    struct ListNode*rightT=NULL;
    struct ListNode*cur=head;
    struct ListNode*next=NULL;
    int n=1;
    while(cur)
    {
        next=cur->next;
        if(n<left)
        {
            if(leftH==NULL&&leftT==NULL)
            {
                leftH=leftT=cur;
                leftT->next=NULL;
            }
            else
            {
                leftT->next=cur;
                leftT=cur;
                leftT->next=NULL;
            }
        }
        else if(n>=left&&n<=right)
        {
            if(midT==NULL&&midH==NULL)
            {
                midH=midT=cur;
                midT->next=NULL;
            }
            else
            {
                cur->next=midH;
                midH=cur;
            }
        }
        else{
            if(rightH==NULL&&rightT==NULL)
            {
                rightH=rightT=cur;
                rightT->next=NULL;
            }
            else{
                rightT->next=cur;
                rightT=cur;
                rightT->next=NULL;
            }
        }
        n++;
        cur=next;
    }
    if(leftH==NULL)
    {
        midT->next=rightH;
        return midH;
    }
    leftT->next=midH;
    midT->next=rightH;
    return leftH;
}