C语言.数据结构.单链表经典算法

数据结构.单链表经典算法

• 1.经典算法OJ题1：移除链表元素
• • 1.1题目描述：
  • 1.2题解：
  • 1.3图文解释：
• 2.经典算法OJ题2：反转链表
• • 2.1题目描述：
  • 2.2题解：
  • 2.3图文解释
• 3.经典算法OJ题3：合并两个有序链表
• • 3.1题目描述：
  • 3.2题解：
  • 3.3图文解释
• 4.经典算法OJ题4：链表的中间节点
• • 4.1题目描述：
  • 4.2题解：
  • 4.3图文解释
• 5.经典算法OJ题5：环形链表的约瑟夫问题
• • 5.1题目描述：
  • 5.2题解：
  • 5.3图文解释
• 6.经典算法OJ题6：分割链表
• • 6.1题目描述：
  • 6.2题解：
  • 6.3图文解释

1.经典算法OJ题1：移除链表元素

题目：移除链表元素

1.1题目描述：

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

1.2题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //创建一个新的空链表来装不为val节点：
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;

    ListNode* pcur = head;
    //找不为val值的节点尾插在空链表中
    while(pcur) {
        if(pcur->val != val) 
        {
            //情况一：链表为空
            if(newhead == NULL) 
            {
                newhead = newtail = pcur;
            }
            else
            {
                //链表不为空：
                newtail->next = pcur;
                newtail = newtail->next;
            }
        }
        pcur = pcur->next;
    }
    if(newtail) 
    {
        newtail->next = NULL;
    }
    return newhead;
}

1.3图文解释：

2.经典算法OJ题2：反转链表

题目：反转链表

2.1题目描述：

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

2.2题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    //判断单链表是否为空：
    if(head == NULL) {
        return head;
    }
    //开始反转：
    ListNode* n1 = NULL;
    ListNode* n2 = head;
    ListNode* n3 = head->next;
    //遍历单链表：
    while(n2) {
        //发生反转：改变指针指向
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3) {
            n3 = n3->next;
        }
    }
    return n1;
}

2.3图文解释

3.经典算法OJ题3：合并两个有序链表

题目：合并两个有序链表

3.1题目描述：

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

3.2题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //判断两个链表是否有空链表出现：
    if(list1 == NULL)
    {
        //证明只有list2存在并且list2本身就是有序的，所以不用合并了
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
    //创建一个带哨兵位的链表，节省判新链表是否为空
    ListNode* newhead, *newtail;
    newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
    ListNode* l1 = list1;
    ListNode* l2 = list2;

    //开始合并：
    while(l1 && l2)
    {
        if(l1->val > l2->val)//哪个节点小，哪个节点就先排序
        {
            newtail->next = l2;
            newtail = newtail->next;
            //l2也得往下走
            l2 = l2->next;
        }
        else
        {
            newtail->next = l1;
            newtail = newtail->next;
            l1 = l1->next;
        }
    }
    //走到这 就会有指针越界访问了,但是还没有把所有的节点尾插在新链表中
    if(l1)
    {
        newtail->next = l1;
    }
    if(l2)
    {
        newtail->next = l2;
    }
    //哨兵位 什么都不表示，有效位置为哨兵位的下一个位置
    ListNode* ret = newhead->next;
    //把哨兵位内存空间释放掉
    free(newhead);
    newhead = NULL;
    return ret;
}

3.3图文解释

4.经典算法OJ题4：链表的中间节点

题目：链表的中间节点

4.1题目描述：

• 给你单链表的头结点 head ，请你找出并返回链表的中间结点。
• 如果有两个中间结点，则返回第二个中间结点。

4.2题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    //定义两个快慢指针：
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next)
    {
        //slow走一步，fast就走两步（一个快，一个慢）
        slow = slow->next;
        fast = fast->next->next;
    }
    //走到这里 正好slow指向了链表的中间位置，两种情况都成立
    return slow;
}

4.3图文解释

5.经典算法OJ题5：环形链表的约瑟夫问题

题目：环形链表的约瑟夫问题

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

5.1题目描述：

• 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
  下一个人继续从 1 开始报数。
  n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
• 数据范围：
  1 ≤𝑛, 𝑚≤10000
  进阶：空间复杂度 𝑂(1)，时间复杂度 𝑂(𝑛)

5.2题解：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
 typedef struct ListNode ListNode;
 //创建节点：
 ListNode* buyNode(int x)
 {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    //看申请空间是否失败：
    if(node == NULL)
    {
        exit(1);//假如申请失败，直接退出程序
    }
    node->val = x;
    node->next = NULL;
    //返回结点的指针
    return node;
 }
 //创建带环链表：
 ListNode* createCircle(int n)
 {
    //先创建一个节点，再串联起来
    ListNode* phead = buyNode(1);
    ListNode* ptail = phead;
    for (int i = 2; i <= n; i++)//n = 5, 再创建4个节点就行了
    {
        ptail->next = buyNode(i);
        //新增一个节点，此时ptail不为尾节点，ptail需往后走，再成为尾节点 
        ptail = ptail->next;
    }
    //首尾相连，变成带环链表
    ptail->next = phead;
    return ptail;
 }
int ysf(int n, int m ) {
    //1.根据n的大小，创建带环链表
    ListNode* prev = createCircle(n);
    ListNode* pcur = prev->next;
    //数到2就退出
    int count = 1;
    while(pcur->next != pcur)
    {
        //数到2，就销毁此节点
        if(count == m)
        {
            prev->next = pcur->next;
            //销毁pcur节点
            free(pcur);
            pcur = prev->next;
            //销毁pcur节点完之后，计数count的下一个又重新变成了1
            count = 1;
        }
        else
        {
            //此处不需要销毁节点，让prev指针走到pcur的位置即可
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    //此时剩下的一个节点一定是要返回的节点的值
    return pcur->val;
}

5.3图文解释

6.经典算法OJ题6：分割链表

题目：分割链表

6.1题目描述：

• 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
• 你不需要 保留 每个分区中各节点的初始相对位置。

6.2题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
    // 假如链表为空，就不用分割了
    if (head == NULL) {
        return head;
    }
    // 创建两个带哨兵位链表：大链表和小链表
    ListNode *lesshead, *lesstail;
    ListNode *greaterhead, *greatertail;
    lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
    greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));

    ListNode* pcur = head;
    // 遍历原链表：
    while (pcur) {
        if (pcur->val < x) {
            // 把pcur尾插在小链表的尾节点上
            lesstail->next = pcur;
            // 尾节点向下挪动一位，重新变成新的尾节点
            lesstail = lesstail->next;
        } else {
            // 把pcur尾插在大链表的尾节点上
            greatertail->next = pcur;
            greatertail = greatertail->next;
        }
        pcur = pcur->next;
    }
    // 避免死循环，得手动改变 第5节点的下一个节点(本身还是指向2节点的)指向NULL
    greatertail->next = NULL;

    // 把小链表的尾节点的下一个节点指向大链表的第一个有效节点,变成一个新的链表
    lesstail->next = greaterhead->next;
    return lesshead->next;
}

6.3图文解释