数据结构：链表经典算法OJ题

目录

前言

一、移除链表元素

二、反转链表

三、合并两个有序链表

四、链表的中间节点

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

---

前言

    在了解了链表的相关知识后，我们还需要一些题目进行练习加深对链表这方面知识的理解，也可以用来检测链表这块学的的怎么样，废话不多说，开始上手。

一、移除链表元素

    这里给上题目链接感兴趣的可以看一下（移除链表元素），

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

 看题目描述，我们需要删除链表中链表节点为特定值的节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
   struct ListNode*a=NULL;
   struct ListNode*b=NULL;
   if(head==NULL)
     return head;
    while(head)
    {
        if(head->val!=val)
        {
            if(a==NULL)
              a=b=head;
            else
            {
                b->next=head;
                b=b->next;
            }
        }
        
        head=head->next;
    }
    if(b)
         b->next=NULL;
    return a;
}

    首先，如果链表本身为空，就可以直接返回一个空指针，如果不为空就可以开始下一个阶段，先创建两个指针a,b指向开始给的头结点，让初始头结点开始遍历，如果遇到节点值为特定值就让b节点指向初始头结点的下一个，相当于跳过了这个节点，最后遍历完，如果b节点不为空，就将b的下一个节点置空，相当于是把那些带有特定值的节点删除了。

二、反转链表

    这里先给上题目链接（反转链表）

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

这里先给上代码，慢慢来讲解一下。 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
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;
}

     首先还是要判断链表是否为空，空链表直接返回就行了，这里需要创建三个指针，在遍历链表时，将当前节点的 next 指针改为指向前一个节点，由于节点没有引用其前一个节点，因此必须事先存储其前一个节点，在更改引用之前，还需要存储后一个节点，最后返回新的头引用。

三、合并两个有序链表

    题目链接（合并有序链表）

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

这道题让我们把两个有序链表合并在一起并且合并后的链表依然有序，这里先上代码，后面讲解。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL)
      return list2;
    if(list2==NULL)
      return list1;
    struct ListNode*n1=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*n2=n1;
    while(list1&&list2)
    {
        if(list1->val<=list2->val)
        {
            n2->next=list1;
            list1=list1->next;
            n2=n2->next;
        }
        else
        {
            n2->next=list2;
            list2=list2->next;
            n2=n2->next;
        }
    }
    if(list1)
      n2->next=list1;
    if(list2)
      n2->next=list2;
    struct ListNode*c=n1->next;
    free(n1);
    n1=NULL;
    return c;
}

 首先判断两个有序链表中是否有空链表，如果有一方为空链表，就可以直接返回另一个链表了，需要开辟一个新的链表，将两个链表的每一个值一一比较排个序，再一个一个的放入新的链表当中。

四、链表的中间节点

    题目链接（链表的中间节点）

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

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

 这道题可以用很多种方式写出来，这里用的是快慢指针的方式，还有计数器法等方式（计数器法就是先遍历一遍链表算出有多少个节点，再除以二，按照除后的数字在遍历一遍到中间节点位子），这里快慢指针法就先上代码，后面讲解。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode*a=head;
    int i=0;
    while(head)
    {
        head=head->next;
        i++;
    }
    int count=i/2;
    while(count>0)
    {
        a=a->next;
        count--;
    }
    return a;
}

让俩个指针开始时同时指向头结点，一个一次走一步，一个每次走两步，在快指针到达尾节点或者空节点时（奇数节点链表和偶数节点链表会不一样），慢指针就会在中间节点的位置（奇数节点指针会在中间节点，偶数节点指针会在中间两个节点的后一个节点），最后输出慢指针就行了。

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

     题目链接（约瑟夫问题）

描述

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

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

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 

 先上代码，后面慢慢讲解。

 
 #include<stdlib.h>
 #include<stdio.h>
typedef struct music
{
    int data;
    struct music* next;
}music;
music*initial(int n)
{
    music*a=(music*)malloc(sizeof(music));
    a->data=n;
    a->next=NULL;
    return a;
}
music*creat(int n)
{
    music*a=initial(1);
    music*b=a;
    for(int i=2;i<=n;i++)
    {
        b->next=initial(i);
        b=b->next;
    }
    b->next=a;
    return b;
}
int ysf(int n, int m ) {
    music*a=creat(n);
    music*head=a->next;
    int count=1;
    while(head->next!=head)
    {
        if(count==m)
        {
            a->next=head->next;
            free(head);
            head=a->next;
            count=1;
        }
        else
        {
            a=head;
            head=head->next;
            count++;
        }
    }
    return head->data;
}

    这道题涉及到了链表的创建，所以就需要一个包含数据成员的结构体以及初始化函数和创建链表相关函数，在实现约瑟夫问题的函数中，先创建head和a指针，head指针就是扮演着正在报数的那个人，a这是head的前一个节点，当报数的head报道特定的数字,a就会跳过这个节点，然后再把这个节点释放掉，head继续在a->next，循环着操作，留下最后一个就可以输出结果了。

---

    本篇内容就到这里了，没到题目都给了链接，可以自己去尝试解题，光听的话效果没那么好。