链表经典算法OJ题目_链表oj题

目录

1.单链表相关经典算OJ题目1：移除链表元素

思路一

代码 ：

 思路二

代码：

 2.单链表相关经典算OJ题目2：反转链表

思路一

代码：

思路二

代码：

 3.单链表相关经典算OJ题目3：链表的中间节点

思路 

代码：

  4.单链表相关经典算OJ题目4：合并两个有序数组

思路 

代码：

  5.单链表相关经典算OJ题目5：环形链表的约瑟夫问题

思路

代码：

    6.单链表相关经典算OJ题目 6 ：分割链表

思路一 

代码：

思路二

 代码：

思路三：

 代码：

---

1.单链表相关经典算OJ题目1：移除链表元素

思路一

直接在原链表里删除val元素，然后让val前一个结点和后一个节点连接起来。

这时我们就需要3个指针来遍历链表：

pcur  —— 判断节点的val值是否于给定删除的val值相等

prev ——保存pcur的前一个节点，为删除节点后，连接pcur之后的节点做准备

del —— 保存pcur之后的一个节点，为删除节点之后，连接链表做准备，和继续遍历链表

那么一开始它们的位置应该怎么放呢？

链表肯定是从第一个节点开始遍历的，那么 pcur 肯定就指向第一个节点，del可以先不给值，等到要删除的时候在把pcur之后的节点赋值给它

prev是在pcur前面的一个节点，我们会发现，当第一次遍历时，pcur前面并没有节点，那么我们就创造一个节点：哨兵卫（Sentinel），于链表连接，再让prev指向它。之后我们在返回新的链表的时候，我们返回 哨兵卫（Sentinel）的下一个节点即可。

代码 ：

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //创建哨兵卫节点并于链表连接
    ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
    newhead->next = head;
 
    ListNode* prev = newhead;
    ListNode* pcur = head;
    ListNode* del;
 
    当我们pcur走到尾节点指向的NULL处时停止循环
    while(pcur)
    {
        //当符合给定的val值，删除
        if(pcur->val == val)
        {
            del = pcur->next;   //记录pcur下一个节点位置
            free(pcur);         //删除pcur节点
            prev->next = del;   //将pcur前后的节点连接起来
            pcur = del;         //走向下一个节点
            
        }
 
        //当不符合给定的val值，继续遍历链表
        else
        {      
            prev = pcur;
            pcur = pcur->next;
        }
    }
 
    //释放不要的哨兵卫节点并返回新的链表
    ListNode* p = newhead->next;
    free(newhead);
 
    return p;
}

 思路二

直接创建一个新的链表，遍历原链表，将不是val值的节点尾插到新的链表中

需要用到两个指针：

pcur —— 用来遍历原链表，找不是val值的节点

ptail —— 新链表的尾节点，将来尾插至此节点后面

代码：

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //创建哨兵卫节点，这里是为了防止对NULL指针解引用。
    ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
    newhead->next =  NULL;
 
    ListNode* newtail,* pcur;
    newtail = newhead;
    pcur = head;
    
    //当pcur走到原尾节点->NULL时停止循环
    while (pcur)
    {
        //如果和给定的val值节点不相等，则尾插至新链表中
        if (pcur->val != val)
        {
            newtail->next = pcur;
            newtail = newtail->next;
        }
        pcur = pcur->next;    //pcur继续遍历原链表
    }
 
    newtail->next = NULL;  //出了循环之后，记得把新的链表的尾节点指向NULL,保证不会带出多余节点
 
    //释放哨兵卫节点
    ListNode* p = newhead->next;
    free(newhead);
 
    return p;
}

 2.单链表相关经典算OJ题目2：反转链表

思路一

创建一个新的链表，将原链表的节点依次拿到新链表进行头插

需要两个指针：

pcur —— 遍历原链表

newhead —— 作为新链表的第一个节点

代码：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
 
    //如果链表为NULL则不用反转
    if(head == NULL)
        {
            return head;
        }
 
    ListNode* newhead = NULL;
    ListNode* pcur = head;
    ListNode* Transfer = NULL;
    
    //开始反转
    while(pcur)
    {
        Transfer = pcur;   // 保存当前节点的指针
        pcur = pcur->next; // 移动到下一个节点
 
        Transfer->next = newhead;  // 反转当前节点的next指针，指向新的头节点
        newhead = Transfer;   // 更新新链表的头节点
    }
 
    return newhead;
}

思路二

创建三个指针，完成链表的反转：

n1 : 记录n2前一个节点

n2 : 用来遍历链表

n3 : 记录n2后一个节点

代码：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    
    //链表为NULL时不用反转
 
    if (head == NULL) {
        return head;
    }
 
    ListNode* n1 = NULL;
    ListNode* n2 = head;
    ListNode* n3 = n2->next;
 
    当n2遍历完链表时循环停止
    while (n2)
    {
 
        n2->next = n1;   //让n2节点指向n1节点
        n1 = n2;         //让n1走至下一个节点
        n2 = n3;         //让n2走至下一个节点
 
      // 因为n3比n2快一步，当n2走至尾节点的时候，n3已经为NULL了，不处理的话会造成NULL的解引用
        if (n3 != NULL)   
            n3 = n3->next;   //让n3走至下一个节点
    }
 
    //当循环结束时n1会成为新的第一个节点
    return n1;
    
}

 3.单链表相关经典算OJ题目3：链表的中间节点

思路 

这一题说难也不难，相信想一下大部分的码农都可以写出来

这里我就介绍一个更妙的方法：快慢指针法

什么是快慢指针法？顾名思义，就是创造两个指针，一个指针走的慢一点，一个指针走的快一点，对应到我们这一题上就是，同一时间内，一个指针走一步，一个指针走两步：2 × slow = fast

那么它是否可以应对题目给出的条件呢？当中间节点有两个时，返回第二个中间节点

两个中间节点

单中间节点

 

可以看见无论是双中间节点 还是 单中间节点这个方法都可以完美解决，我们也可以观察出循环的结束条件为：当 fast 指针为NULL 或 fast指针下一个节点为NULL时停止

代码：

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    
    //创建快慢指针
    ListNode *slow,*fast = NULL;
    
    链表不为NULL时快慢指针从第一个节点开始遍历
    if(head != null);
    slow = fast = head;
 
    //当 fast 指针为NULL 或 fast指针下一个节点为NULL时停止
    //这两个表达式位置不可以换，若换，当fast为NULL时会出现对NULL指针解引用
    //如果换，当fast为NULL时，第一个表达式为假，第二个表达式就不执行了，不会出现NULL指针解引用
    while(fast ！= NULL && fast->next)
    {
        slow = slow->next;        //慢指针走一个节点
        fast = fast->next->next;  //快指针走两个节点
    }
 
    return sl
}

  4.单链表相关经典算OJ题目4：合并两个有序数组

  

思路 

创建新链表，并且通过遍历两个原来的链表比较大小来添加至新的链表中

代码：

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
 
    //设置哨兵节点当新链表的第一个节点
    ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
    newhead->next = NULL;
    ListNode* newtail = newhead; //只有一个节点，第一个节点 = 尾节点
 
    //创建l1 l2 指针遍历原链表list1 list2
    ListNode* l1 = list1;
    ListNode* l2 = list2;
 
    //当遍历完一个链表时，循环停止，不可能出现两个链表同时遍历完的情况
    while(l1 != NULL && l2 != NULL)
    {
        
        //l1 或 l2 指向的值，小的放入新链表，并让其指针l1或l2 与 newtail指针往后走
        if(l1->val < l2->val)
        {
            newtail->next = l1;
            l1 = l1->next;
            newtail = newtail->next;
        }
        else
        {
            newtail->next = l2;
            l2 = l2->next;
            newtail = newtail->next;
        }
    }
 
    //将没有遍历完的链表，将其内的元素一次性插入新链表中
    if(l1 != NULL)
    {
        newtail->next = l1;
    }
    else
    {
        newtail->next = l2;
    }
 
    //存储哨兵卫后面的节点，并释放哨兵卫节点
    ListNode* p = newhead->next;
    free(newhead);
    
    return p;    //返回新的头节点
}

  5.单链表相关经典算OJ题目5：环形链表的约瑟夫问题

思路

利用我们的环形链表，依次的去遍历链表，使用count计数器计数，当count = m时删除节点，当环形链表只剩一个节点（这个节点下一个节点指向自己）时，就说明找到了最后留下的人。

这时我们需要用到两个指针：

pcur —— 遍历环形链表

prev —— 保存pcur的前一个节点，为删除节点做准备

代码：

typedef struct ListNode ListNode;
 
//创建新节点
ListNode* Buynode(int x){
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    p->val = x;
    p->next = NULL;
    return p;
}
 
//创建环形链表
ListNode* creatCircle(int n){
 
 
    ListNode* head,*ptail;    
    head = Buynode(1);      //创建第一个节点val值为1
    ptail = head;
 
    for(int i = 2;i <= n;i++)     //继续创建节点,直到节点数 = n ，从第一个节点val = 1
    {                             //第二个 = 2....一直到n个节点，其val = n
        ptail->next = Buynode(i);
        ptail = ptail->next;
    }
 
    // 让链表的头尾相连
    ptail->next = head;
 
    //因为要用到第一个节点的上一个节点，所以返回ptail
    return ptail;
}
 
 
int ysf(int n, int m ) {
 
    ListNode* prev,*pcur;    //创建所需要的指针
 
    prev = creatCircle(n);   //创建环形链表
    pcur = prev->next;       //pcur从没有相连的第一个节点开始遍历
    int count = 1;           //创建计数器
 
    //开始循环，当环形链表中的节点指向自己时，说明只剩一个节点，循环结束
    while(pcur->next != pcur)
    {
 
        //如果计数器 == m 则删除该节点
        if(count == m)
        {
            prev->next = pcur->next;  //prev->next指向需删除节点的下一个节点
            free(pcur);               //删除该节点
            pcur = prev->next;        //pcur走向已删除节点的下一个节点
            count = 1;                //重置计数器
        }
 
        //如果计数器 != m 则删除该节点
        else
        {
            prev = pcur;            //两个指针都走向各自的下一个节点
            pcur = pcur->next;
            count++;                //计数器++
        }
    }
 
    
    return pcur->val;     //返回最后一个节点的val值
}

    6.单链表相关经典算OJ题目 6 ：分割链表

思路一 

修改原链表，把小于特定的 x 值尾插到链表后面

pcur —— 遍历链表直到原尾节点

prev —— pcur的前一个节点，为了删除节点准备

patil —— 原尾节点

newpatil —— 新的尾节点

newhead —— 一个哨兵节点作为新的头节点

代码：

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
 
    //如果链表尾为NULL则不用分割
    if(head == NULL)
    {
        return head;
    }
 
    //创建哨兵卫并于链表第一个节点连接，让它成为新的第一个节点
    ListNode* newhead = (ListNode*)malloc(sizeof(ListNode));
    newhead->next = head;
 
    //分割链表需要用到的指针
    ListNode* prev,*pcur,*ptail,*newptail;
    prev = newhead;
    pcur = head;
 
    //找尾节点
    while(pcur->next != NULL)
    {
        pcur = pcur->next;
    }
    ptail = pcur;
    newptail = pcur;
    pcur = head;   //pcur重新回到原第一个节点
 
    //当pcur遍历到原尾节点的时候停止循环
    while(pcur != ptail)
    {
 
        //如果节点的val值比x大，则把节点尾插至链表
        if(pcur->val >= x)   
        {
           prev->next = pcur->next;      //先让prev的下一个节点指向pcur下一个节点
           newptail->next = pcur;       //pcur节点尾插至链表后
           newptail = newptail->next;  //新的尾节点
           pcur = prev->next;         //让pcur走到prev指向的下一个节点
        }
 
        //否者pcur与prev各自往后走一个节点
        else
        {
            prev = pcur;
            pcur = pcur->next;
        }
    }
 
    newptail->next = NULL;断绝尾节点后面还带着其它节点
 
    
    ListNode* p = newhead->next;
    free(newhead);
    
 
    return p;
}

思路二

创建一个新的链表，把大于等于x的节点尾插到新的链表中，小于x的节点头插至链表中

 代码：

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    if(head == NULL)
    {
        return head;
    }
    
    //新链表起码要有一个节点，不然不知道是头插还是尾插
    ListNode* newhead,*pcur,*newptail,*del;
    newhead = newptail = pcur = head;   //把原链表的第一个节点给到新链表
                                        //这时新链表 头 = 尾 
 
    pcur = del = pcur->next;   //pcur走到原链表的第二个节点
 
    //当pcur走到NULL时说明已经遍历完原链表
    while(pcur)
    {
 
        //尾插
        if(pcur->val >= x)
        {
            if(del)                     //怕出现NULL指针解引用
            del = pcur->next;          //存储pcur下一个节点，不然待会找不到
            newptail->next = pcur;     //让新链表尾节点指向pcur
            newptail = newptail->next;   //更习新链表的尾节点
            pcur = del;                 //pcur走向下一个节点
        }
 
        //头插
        else
        {
            if(del)                    //怕出现NULL指针解引用
            del = pcur->next;          //存储pcur下一个节点，不然待会找不到
            pcur->next = newhead;      //pcur的这个节点头插至新链表第一个节点处
            newhead = pcur;            //更新新链表的第一个节点
            pcur = del;                 //pcur走向下一个节点
        }
 
    }
 
    //让新链表的尾节点指向NULl，防止有别的节点被带上
    newptail->next = NULL;
 
    return newhead;
}

思路三：

创建 一大  一小 两个链表 ，把大于等于点放到大链表中，小于x的节点放到小链表中，当原链表的节点被全部放置完毕，把大链表链接到小链表后面。

 代码：

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
 
    //链表为NULL直接返回链表
    if(head == NULL)
    {
        return head;
    }
 
    //创建大链表的第一个节点，和尾节点
    ListNode* Bnewhead,*Bnewptail;
    Bnewhead = Bnewptail = (ListNode*)malloc(sizeof(ListNode));
    
    //创建小链表的第一个节点，和尾节点
    ListNode* Snewhead,*Snewptail;
    Snewhead = Snewptail = (ListNode*)malloc(sizeof(ListNode));
 
    ListNode* pcur = head;   //遍历原链表指针
    while(pcur)
    {
 
        //尾插至大链表
        if(pcur->val >= x)
        {
            Bnewptail->next = pcur;       //将大于等于x的pcur节点尾插至大链表
            Bnewptail = Bnewptail->next;  //更新大链表尾节点
        }
 
        //尾插至小链表
        else
        {
            Snewptail->next = pcur;       //将小于x的pcur节点尾插至小链表
            Snewptail = Snewptail->next;   //更新小链表尾节点
            
        } 
        pcur = pcur->next;              //让pcur继续遍历原链表下一个节点
    }
    Bnewptail->next = NULL;     //让大链表的尾节点的下一个节点指向NULL防止它带出其他节点
    Snewptail->next = Bnewhead->next;   //让小链表的尾节点的下一个节点指向大链表的第一个节点
 
    //释放动态申请的空间
    ListNode* ret= Snewhead->next;   //存储大小合并后的链表的第一个有效节点
    free(Bnewhead);                 
    free(Snewhead);
    Bnewhead = Snewhead = NULL;
 
    //返回新链表
    return ret;
    
}