leetcode每日一练：链表OJ题

链表经典算法OJ题

1.1 移除链表元素

题目要求：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

解题思路：

思路1：

定义两个指针，一个指向当前节点，一个指向当前节点的下一个节点，如果下一个节点是要删除的节点就将当前节点的next存储下一个节点的再下一个节点的地址，然后free那个节点。知道遍历完原链表，该思路是改变原链表。

思路2：

建立一个新的链表，遍历原链表，将原链表中的非删除节点给新的链表，遍历结束后新链表中没有要删除节点。

struct ListNode{
    int val;
    struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* Newhead, * NewTail;//一个头链表，一个链表尾部
    Newhead = NewTail = NULL;
    //遍历原链表
    struct ListNode* pcur = head;
    while (pcur){
        if (pcur->val != val){
            if (Newhead == NULL){
                Newhead = NewTail = pcur;
            }
            else{
                NewTail->next = pcur;
                NewTail = NewTail->next;
            }
        }
        pcur = pcur->next;
    }
    //如果要删除值在原链表为节点,新链表的尾节点就不会指向NULL，所以这里要判断
    if (NewTail){
        NewTail->next = NULL;
    }
    return Newhead;
}

1.2 反转链表

题目要求：

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

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路：

可以定义三个新的节点类型的指针变量n1、n2、n3。然后就可以使用这三个指针来反转链表。首先n1初始化为NULL，n2初始化为head链表头结点，n3则是head头结点的下一个节点。然后循环n2->next = n1， n1 = n2， n2 = n3，n3 = n3->next。循环往复就完成了反转链表的操作。

typedef struct ListNode{
    int val;
    struct ListNode *next;
}*pList;

//反转链表函数实现
pList reverselist(pList head){
    if (head == NULL){
        return NULL;
    }
    pList n1, n2, n3;
    n1 = NULL, n2 = head, n3 = head->next;
    while (n2){
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)//如果n3为NULL就不再向后访问了
           n3 = n3->next;
    }
    return n1;
}

//以下调用上面函数的main是我自己写的，可以供大家参考
int main()
{
    //创建链表
    struct ListNode* phead, *pTail, *p;
    phead = pTail = NULL;
    int n = 0;
    printf("请输入要创建链表节点个数:>");
    scanf("%d", &n);
    int i = 0;
    for (i = 0; i < n; i++)
    {
        p = (pList)malloc(sizeof(struct ListNode));
        printf("请输入第%d个节点的值:>", i + 1);
        scanf("%d", &(p->val));
        p->next = NULL;
        if (phead == NULL)
        {
            phead = p;
            pTail = phead;
        }
        else
        {
            pTail->next = p;
            pTail = pTail->next;
        }
    }
    //调用反转链表函数
    pList Newhead = reverselist(phead);
    if (Newhead == NULL)
    {
        perror("reverselist");
        return;
    }
    phead = Newhead;
    //打印链表节点数据
    while (Newhead)
    {
        printf("%d->", Newhead->val);
        Newhead = Newhead->next;
    }
    printf("NULL\n");
    i = 1;
    Newhead = phead;
    //销毁链表
    while (Newhead)
    {
        phead = phead->next;
        free(Newhead);
        Newhead = phead;
        printf("已释放第%d条节点\n", i);
        i++;
    }
    return 0;
}

1.3 合并两个有序链表

题目要求：

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

解题思路：

定义两个新的节点指针，一个头节点，一个尾结点。比较两个原链表当前节点的数据大小，然后插入新的链表，知道插完为止

typedef struct ListNode {
    int val;
    struct ListNode* next;
}*pList;
//合并两个有序链表函数实现
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL){
        return list2;
    }
    if (list2 == NULL){
        return list1;
    }
    struct ListNode* cur1, *cur2;
    cur1 = list1, cur2 = list2;
    struct ListNode* phead, * pTail;
    phead = pTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while (cur1 && cur2) {
        if (cur1->val < cur2->val){
            pTail->next = cur1;
            pTail = pTail->next;
            cur1 = cur1->next;
        }
        else{
            pTail->next = cur2;
            pTail = pTail->next;
            cur2 = cur2->next;
        }
    }
    if (cur1) {
        pTail->next = cur1;
    }
    if (cur2) {
        pTail->next = cur2;
    }
    struct ListNode* retList = phead->next;
    free(phead);
    return retList;
}
//以下创建链表调用函数的代码是自己写的，只为调用上面函数，不是链表规范创建。仅供参考
int main()
{
    struct ListNode* phead1, pTail1, p1;
    struct ListNode* phead2, pTail2, p2;
    phead1 = pTail1 = NULL;
    phead2 = pTail2 = NULL;
    int n = 0;
    printf("请输入要创建p1和p2链表节点个数:>");
    scanf("%d", &n);
    int i = 0;
    for (i = 0; i < n; i++)
    {
        p1 = (pList)malloc(sizeof(struct ListNode));
        p2 = (pList)malloc(sizeof(struct ListNode));
        printf("请输入p1链表第%d个节点的值:>", i + 1);
        scanf("%d", &(p1->val));
        printf("请输入p2链表第%d个节点的值:>", i + 1);
        scanf("%d", &(p2->val));
        p1->next = NULL;
        p2->next = NULL;
        if (phead1 == NULL && phead2 == NULL)
        {
            phead1 = p1;
            pTail1 = phead1;
            phead2 = p2;
            pTail2 = phead2;
        }
        else
        {
            pTail1->next = p1;
            pTail1 = pTail1->next;
            pTail2->next = p2;
            pTail2 = pTail2->next;
        }
    }
    pList Newhead = mergeTwoLists(phead1,phead2);
    if (Newhead == NULL)
    {
        perror("reverselist");
        return;
    }
    pList phead = Newhead;
    while (Newhead)
    {
        printf("%d->", Newhead->val);
        Newhead = Newhead->next;
    }
    printf("NULL\n");
    i = 1;
    Newhead = phead;
    while (Newhead)
    {
        phead = phead->next;
        free(Newhead);
        Newhead = phead;
        printf("已释放第%d条节点\n", i);
        i++;
    }
    return 0;
}

1.4 链表的中间节点

题目要求：

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
示例 2：
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

解题思路：

快慢指针：使用快慢指针来遍历链表，慢指针每次走一步，快指针每次走两步，当快指针走到最后慢指针刚好走到中间节点。因为快指针是慢指针的2倍。所以快指针从起点到终点时慢指针就是这个路程的一半，是中点。

typedef struct ListNode{
    int val;
    struct ListNode* next;
}*pList;
//函数实现
struct ListNode* middleNode(struct ListNode* head) {
    if (head == NULL){
        return NULL;
    }
    struct ListNode* slow, *fast;
    slow = fast = head;
    //节点数可能是奇数个也可能是偶数个，所以要两种判断
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

1.5 环形链表的约瑟夫问题

著名的Josephus问题

据说著名的历史学家 Josephus有过以下的故事：故事据说发生在古罗马时期，在罗马人占领乔塔帕特后，39个犹太人与约瑟夫及他的朋友躲到一个洞中，他们宁愿死也不要被敌人抓到，于是约定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下1个人重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

题目要求：

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围： 1≤𝑛,𝑚≤100001≤n,m≤10000

进阶：空间复杂度 𝑂(1)O(1)，时间复杂度 𝑂(𝑛)O(n)

示例1

输入：
5,2     
复制返回值：
3    
复制说明：
开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开
1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开
1，3，5，从5开始报数，5->1，1->2编号为1的人离开
3，5，从3开始报数，3->1，5->2编号为5的人离开
最后留下人的编号是3      
示例2

输入：
1,1
返回值：
1

typedef struct ListNode ListNode;

创建一个节点并返回
ListNode* ListBuyNode(int val)
{
    ListNode* ret = (ListNode*)malloc(sizeof(ListNode));
    if(ret==NULL)
    {
        perror("malloc");
        return NULL;
    }
    ret->val = val;
    ret->next = NULL;
    return ret;
}
//创建一个环形链表并返回
ListNode* CreatNode(int n)
{
    ListNode* phead = ListBuyNode(1);
    ListNode* pTail = phead;
    int i = 0;
    for(i=2;i<=n;i++)
    {
        pTail->next = ListBuyNode(i);
        pTail = pTail->next;
    }
    pTail->next = phead;//将链表循环
    return pTail;
}

int ysf(int n, int m ) {
    // write code here
    ListNode* prev = CreatNode(n);
    ListNode* cur = prev->next;
    int count = 1;
    //遍历判断
    while(cur->next!=cur){
        if(count == m){
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
            count = 1;
        }
        else{
            prev = cur;
            cur = cur->next;
            count++;
        }
    }
    return cur->val;
}

1.6 分隔链表

题目要求：

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]

解题思路：

大小链表：我们可以创建两个新的链表，为大小链表。遍历原链表。大于等于x的节点连接在大链表，小于x的节点连接在小链表。最后将大链表的头结点连接在小链表的尾结点。返回小链表的头结点

typedef struct ListNode {
    int val;
    struct ListNode* next;
}*pList;

//分隔链表的函数实现
struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL){
        return NULL;
    }
    struct ListNode* lessHead, * lessTail;
    struct ListNode* greaterHead, * greaterTail;
    //定义哨兵位
    lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* pcur = head;//用来遍历原链表
    //分隔操作
    while (pcur){
        if (pcur->val >= x){
            greaterTail->next = pcur;
            greaterTail = greaterTail->next;
        }
        else{
            lessTail->next = pcur;
            lessTail = lessTail->next;
        }
        pcur = pcur->next;
    }
    //将大小链表连接起来
    lessTail->next = greaterHead->next;
    if(greaterTail)
       greaterTail->next = NULL;
    //释放哨兵位
    free(greaterHead);
    struct ListNode* retList = lessHead->next;
    free(lessHead);
    //返回头结点
    return retList;
}
int main()
{
    pList phead, pTail, p;
    phead = pTail = NULL;
    int n = 0;
    printf("请输入要创建链表节点个数:>");
    scanf("%d", &n);
    int i = 0;
    for (i = 0; i < n; i++)
    {
        p = (pList)malloc(sizeof(struct ListNode));
        printf("请输入第%d个节点的值:>", i + 1);
        scanf("%d", &(p->val));
        p->next = NULL;
        if (phead == NULL)
        {
            phead = p;
            pTail = phead;
        }
        else
        {
            pTail->next = p;
            pTail = pTail->next;
        }
    }
    pList Newhead = partition(phead, 3);
    if (Newhead == NULL)
    {
        perror("reverselist");
        return;
    }
    phead = Newhead;
    while (Newhead)
    {
        printf("%d->", Newhead->val);
        Newhead = Newhead->next;
    }
    printf("NULL\n");
    i = 1;
    Newhead = phead;
    while (Newhead)
    {
        phead = phead->next;
        free(Newhead);
        Newhead = phead;
        printf("已释放第%d条节点\n", i);
        i++;
    }
    return 0;
}