[数据结构与算法]单链表典例1.0

一：?移除链表元素

?

.基本思路：1）判断链表是否为空，若为空返回NULL

2）遍历链表，找到val对应前的节点，与val的next节点链接。

??????? 3）坑点：会出现头节点为val的情况，所以要额外处理一下头节点的问题。

本题采用双指针更方便点。

画图

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    while(head&&head->val==val)//找新的头节点，改新头节点的head->val!=val
    {
        head = head->next;//更新head
    }
    if(head==NULL)//判断新头节点是否出现示例2或示例3的极端情况
    {
        return NULL;
    }
    struct ListNode* prev = head;//创建指针，记录当前head的地址
    while(prev->next)
    {
        if(prev->next->val == val)//判断节点val的值是否与val相等。
        {
            prev->next = prev->next->next;//相等就进行2）中的链接
        }
        else 
        {
            prev = prev->next;//更新prev
        }
    }
    return head;
}

二：

反转链表

基本思路：1）判断链表是否为空，如果为空，就返回NULL

2）处理方法：

i构建一个新的头节点，将原先的数据进行尾插

ii改变原先箭头的指向问题

画图：

i。

注意：循环结束条件是cur==NULL

每次都需要更新cur和newHead，最后返回newHead

由于cur为空时才结束循环，会是得next成为空指针，要特殊处理

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL)//判断链表是否为空
    {
        return NULL;
    }
    struct ListNode* newHead = NULL,*cur = head,*next = head->next;
    while(cur)
    {
        cur->next = newHead;//头插节点
        newHead = cur;//更新节点newHead
        cur = next;//更新cucr指针
        if(next!=NULL)//防止next成为野指针
        next = next->next;//更新next指针
    }
    return newHead;
}

ii。强行逆转箭头

注意：1）为了方便处理，设置了三个指针变量：prev，cur，next，分别记录cur前中后的节点。

?? 2）与上图思路相似，还是链接和更新节点

画图：

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)//判断链表是否为空
        return NULL;
    struct ListNode* prev = NULL;//
    struct ListNode* cur = head;//
    struct ListNode* next = head->next;//创建指针变量

    while(cur)//循环
    {
        cur->next = prev;//链接节点
        prev = cur;//更新prev
        cur = next;//更新cur
        if(next)//防止next成为野指针
            next = next->next;//更新next
    }
    return prev;
}