数据结构：链表算法题

题1.删除链表中的某个元素val

题目表述：

思路1:在源链表中进行删除更改

1.利用循环遍历链表

2.在遇到要删除的元素时，将该节点后的节点地址保存到要删除的节点前的节点内部。

3.保证新链表的末尾地址内指向的下一个节点的地址为空指针。

3.返回源链表的首节点地址。
这个比较简单，就不再演示了。

思路2:创建一个新链表

需要的数据:新链表的首地址以及𮧵地址，源文件的首节点地址

1.利用循环遍历整个链表

2.在遍历链表，链表的地址逐一传给新链表，遇到要删除的数据，不传给新链表，将源链表地址向后移位一个节点

3.保证新链表的末尾地址内指向的下一个节点的地址为空指针。

4.返回新链表的首节点地址。
代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode* newhead=NULL,*newtail=NULL;
    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;
    }
    if(newtail)
    {
        newtail->next=NULL;
    }
    return newhead;
}

题2:反转一个链表

问题描述：

案例：

思路1:在源链表内部进行操作

1.创建三个变量ps1，ps2，ps3
2.将ps1设为NULL，ps1指向第一个节点位置，ps2指向ps1下一个节点：ps2=ps1->next
具体如图：

4.返回链表的头结点地址。
代码实现：

/**
 * 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* ps1,*ps2,*ps3;
    ps1=NULL;ps2=head;ps3=ps2->next;
    while(ps2)
    {
        ps2->next=ps1;
        ps1=ps2;
        ps2=ps3;
        if(ps2)
            ps3=ps2->next;
    }
    return ps1;
}

这个思路不太好描述，可能描述出来不太好理解，但是直到这个思路的会发现它其实跟创建一个新链表，然后让节点一个一个头插到新链表里面的思路相似，所以就引出了我们的思路2.

思路2:创建一个新链表

数据需求:创建两个指针，一个指向头结点，一个指向尾节点。

1.利用循环遍历数组

2.将每个节点头插到新链表

3.将新链表的尾节点内指针置为空指针

4.返回新链表的头结点地址
代码实现：

/**
 * 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* ,*newtail;
    newhead=newtail=NULL;
    ListNode* pcur=head;
    while(pcur)
    {
        if(newhead  ==NULL)
        {
            newhead =newtail=pcur;
            pcur=pcur->next;
        }
        else
        {
            ListNode* ps=pcur->next;
            pcur->next=newhead;
            newhead=pcur;
            pcur=ps;
        }
    }
    newtail->next=NULL;
    return newhead;
}

题3:寻找链表中间位置

题目描述:

示例：

思路1:

1.遍历一遍链表，统计链表节点个数

2.将链表节点数目除2，找到中间节点的位置

3.第二次遍历链表，找到中间位置的节点并返回该节点的地址。
这个思路很简单，有兴趣的下去可以自行尝试一下。

思路2:快慢指针

1.定义两个指针，同时指向头结点

2.一个指针向后移位一个节点，一个指针向后移位两个节点，以此类推，当快节点走到末尾节点时，第一个节点就刚好停在了中间节点的位置，在这里分两种情况，节点数目为奇数或者偶数:

1.节点数目为奇数:

2.节点数目为偶数:

3.返回慢指针的地址

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* ps1,*ps2;
    ps1=ps2=head;
    while(ps2&&ps2->next)
    {
        ps1=ps1->next;
        ps2=ps2->next->next;   
    }
    return ps1;
}

快慢指针理解图示：

由上图可知，循环结束的条间为ps为空或者ps->next为空，所以他们都不为空时循环继续。
但是循环判断条件前后顺序不可更改。
当ps2为空时，ps2->next就会对空指针解引用，会报错。
---------------------------------------------------------------------------分隔符
有错请在评论区指正，谢谢
本次介绍就结束了，编写不易，看官老爷们赏个三连吧。