数据结构——链表专题1

一、移除链表元素

原题链接：移除链表元素

一个解法是遍历原链表，将与val相等的结点抛弃，链接后一个结点

另一个解法是创建一个新的链表，不保存与val相等的结点

注意：新的链表如果还没有插入结点，首先应该先将目的结点成为首结点
并且最后的尾结点的next应该置空

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur =  head;
    struct ListNode* phead = NULL;
    struct ListNode* ptail = NULL;
    while(cur)
    {
        if(cur->val != val)
        {
            //设置头结点
            if(phead == NULL)
            {
                phead = ptail = cur;
            }
            else
            {
                //尾插
                ptail->next = cur;
                ptail = ptail->next;
            }
        }
        cur = cur->next;
    }

    if(ptail)
    {
        ptail->next = NULL;
    }
    return phead;
}

二、反转链表

原题链接：反转链表

一种解法是创建一个新的链表，遍历原链表，倒着储存进新的链表

另一个解法比较巧妙，需要三个指针

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

三、合并两个有序链表

原题链接：合并两个有序链表

思路：创建一个新的链表，将上面两个链表遍历，将小的结点先储存在新的链表中
最后要么list1先遍历完，要么list2先遍历完，在写一个判断，将没有遍历完的链表的结点直接尾插到新的链表的末尾

注意：我们可以先创建一个哨兵位，方便我们直接插入数据，不在判断新的链表是否为空

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{

    if(list1 == NULL)
    {
        return list2;
    }

    if(list2 == NULL)
    {
        return list1;
    }
    //创建哨兵位
    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* ptail = phead;
    struct ListNode* pcur1 = list1;
    struct ListNode* pcur2 = list2;
    while(pcur1 && pcur2)
    {
        if(pcur1->val < pcur2->val)
        {
            ptail->next = pcur1;
            ptail = ptail->next;
            pcur1 = pcur1->next;
        }
        else
        {
            ptail->next = pcur2;
            ptail = ptail->next;
            pcur2 = pcur2->next;
        }
    }
    if(pcur1)
    {
        ptail->next = pcur1;
    }
    if(pcur2)
    {
        ptail->next = pcur2;
    }
    struct ListNode* ret = phead->next;
    free(phead);
    phead = NULL;
    return ret;
}

四、链表的中间节点

原题链接：链表的中间节点

使用快慢指针可以很好的解决这个问题

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

五、环形链表的约瑟夫问题

原题链接：环形链表的约瑟夫问题


这个问题起源于一个故事：

著名的Josephus问题 据说著名犹太历史学家 Josephus有过以下的故事：在罗⻢⼈占领乔塔帕特后，39个犹太⼈与
Josephus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死也不要被⼈抓到，于是决定了⼀个⾃杀
⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀，然后再由下⼀ 个重新报数，直到所有⼈都⾃杀⾝亡为⽌。
历史学家 然⽽Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在
第16个与第31个位置，于是逃过了这场死亡游戏。

解决这道题，可以创建一个环形链表（循环链表），将题目的数据储存在链表的结点里面

然后创建两个指针，一个指向头结点，一个指向尾结点

如果满足条件，遇到要删除的结点，先将prev->next指向pcur->next，然后释放pcur结点，再将pcur结点往后移动一次

如果不满足条件，移动pcur和prev一次即可

注意：最后的循环结束条件是pcur->next = pcur，即只剩下一个结点，而不是pcur->next = prev，因为它们两个可能在移动中重合

//创建结点
struct ListNode* BuyNode(int x)
{
    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(newnode == NULL)
    {
        exit(1);
    }
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}
//创建环形链表
struct ListNode* CreatCirle(int n)
{
    struct ListNode* phead = BuyNode(1);
    struct ListNode* ptail = phead;
    for(int i = 2;i <= n;i++)
    {
        ptail->next = BuyNode(i);
        ptail = ptail->next;
    }
    //将尾结点和头结点连接起来
    ptail->next = phead;
    return ptail;
}
int ysf(int n, int m )
{
   int count = 1;
   struct ListNode* prev = CreatCirle(n);
   struct ListNode* pcur = prev->next;
   
   while(pcur->next != pcur)
   {
        if(count == m)
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;
        }
        else
        {
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
   }
   return pcur->val;
}

六、分割链表

原题链接：分割链表

解法一：创建两个新的链表，小的放在一起，大的放在一起，最后将小的链表后面合并上大的链表
解法二：在原链表的基础上，遍历链表，将小的位置不变，将大的尾插到链表的最后，删除前面的大的结点
解法三：创建一个新的链表，将小的结点头插，大的结点尾插

下面我们围绕解法一来解决这道题

为方便在新的链表里面插入结点，我们可以创建哨兵位，最后释放哨兵位就行了
注意：在合并后的链表里面，最后的结点的next一定要置为空并且它的位置在合并链表之前，因为大的链表如果没有结点，则只有一个哨兵位，没有next的指向，交换位置后会使用next指针导致出现错误

struct ListNode* partition(struct ListNode* head, int x)
{
    //空链表
    if(head == NULL)
    {
        return head;
    }

    //创建小的链表
    struct ListNode* lessnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* lesstail = lessnode;

    //创建大的链表
    struct ListNode* greaternode = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* greatertail = greaternode;

    //遍历链表
    struct ListNode* pcur = head;
    while(pcur)
    {
        if(pcur->val < x)
        {
            lesstail->next = pcur;
            lesstail = lesstail->next;
        }
        else
        {
            greatertail->next = pcur;
            greatertail = greatertail->next;
        }
        pcur = pcur->next;
    }
    //将新的链表最后一个置为空
    greatertail->next = NULL;
    //合并链表
    lesstail->next = greaternode->next;
    
    struct ListNode* phead = lessnode->next;
    //释放哨兵位
    free(lessnode);
    lessnode = NULL;
    free(greaternode);
    greaternode = NULL;
    return phead;
}