单链表面试题，看看你的链表是否过关_struct listnode* reverse(struct listnode* head) {

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

原题链接：移除链表元素.

方法一：将值不等于val的结点重新链接成一条新链表

struct ListNode* removeElements(struct ListNode* head, int val){
    //为空，返回NULL
    if(head==NULL)
        return  NULL;   
    //创建一个新链表，将不是val的结点链接在一起
    struct ListNode* newhead=NULL,*tail=NULL;
    struct ListNode* cur=head;
    while(cur)
    {
        struct ListNode* next=cur->next;//迭代
        if(cur->val==val)
        {
            free(cur);
        }
        else
        {
            if(tail==NULL)
            {
                newhead=tail=cur;//让newhead成为头指针
            }
            else
            {
                tail->next=cur;
                tail=cur;
            }
        }
        cur=next;
    }
    //这里要注意，有可能最后一个结点不是需要删除的，那么next需要置空
    if(tail)
        tail->next=NULL;
    return newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

方法二：创建一个哑结点（附加头结点），修改指针指向：p->next = p->next->next；删除值为val的结点

struct ListNode* removeElements(struct ListNode* head, int val){
	if(head==NULL)
	        return head;
    struct ListNode*phead=malloc(sizeof(struct ListNode));
    phead->next=head;
    struct ListNode*p=phead;
    //p->next进行遍历，设置哑结点，有可能删除头结点,从头开始进行遍历
    while(p->next!=NULL)
    {
        if(p->next->val==val)
        {
            p->next=p->next->next;//删除val结点
        }
        else
        {
            p=p->next;
        }
    }

    struct ListNode* cur = phead->next;//记得用cur结点替换，
    free(phead);//释放开辟的phead
    return cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

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

原题链接：反转链表.

方法一：递归
1、先写递归出口，head或者head->next为空，返回head
2、创建新的头newhead，然后遍历到尾结点
3、让自己的下一个节点指向自己，head->next->next = head
4、返回新的头结点newhead

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    struct ListNode* newhead = reverseList(head->next);//一直找到尾结点
    head->next->next = head;//让自己的下一个结点指向自己
    head->next = NULL;
    return newhead;
}
1
2
3
4
5
6
7
8
9
10

方法二：迭代
1、创建三个结点，其中n1为新头指针，n2和n3为迭代结点
2、进入循环迭代，最后返回n1

struct ListNode* reverseList(struct ListNode* head){
	if(head==NULL)
	        return head;
    struct ListNode* n1,*n2,*n3;
    n1=NULL,n2=head,n3=head->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
            n3=n3->next;
    }
    return n1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法三：迭代
1、思路跟方法二差不多，这里就不过解释了

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* p=NULL,*q=NULL;
    struct ListNode*cur=head;
    while(cur)
    {
        q=cur->next;
        cur->next=p;
        p=cur;
        cur=q;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

3、反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

原题链接：反转链表 II.

方法一：穿针引线
1、先找到 left 和 right 的结点
2、在将 left 到 right 范围的结点逆置
3、在将对应结点链接起来即可

prev：left的前一个结点
mid：left结点，也是判断p的归属的条件
tail：right的下一个结点
cur、q、p是迭代逆置的结点

struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
    if(head == NULL || head->next == NULL)//为空，或者一个结点直接返回NULL
        return head;
    if(left == right)//相等变化无意义
        return head;
    struct ListNode* prev = head;//保留left的前一个结点
    struct ListNode* cur = head;
    int x = left;
    int y = left;
    //走到left点
    while(x > 1)
    {
        prev = cur;
        cur = cur->next;
        x--;
    }
    struct ListNode* mid = cur;//用来判断第一个结点是否被反转
    //走到right点
    struct ListNode* next = cur;
    while(left < right)
    {
        next = next->next;
        left++;
    }
    struct ListNode* tail = next->next;//保留right的下一个结点
    struct ListNode* q = NULL, *p = NULL;
    left = y;
    //逆置left到right中间的节点
    while(left <= right)
    {
        q = cur->next;
        cur->next = p;
        p = cur;
        cur = q;
        left++;
    }
    //如果left不在第一个结点，则left的前一个结点指向p
    if(mid == head)
        head = p;
    else
        prev->next = p;
    mid->next = tail;
    return head;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

---

4、链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

原题链接：链表的中间结点.

方法一：双指针
1、一个快指针，一个慢指针，一起走，结束条件：快指针或快指针的下一个结点为空

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10

方法二：查找法
1、先求出整体链表的长度：n
2、在找到 n/2 处即为中间结点

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* p=head;
    int len=0;
    while(head)
    {
        ++len;
        head=head->next;
    }
    int j=0;
    while(p&&j<len/2)
    {
        p=p->next;
        j++;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

5、链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。

输入：1,{1,2,3,4,5}
返回：{5}

原题链接：链表的到时第k个结点.

方法一：
1、定义快慢指针，让快指针先走k步
2、快慢指针在一起走

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* slow = pListHead, *fast = pListHead;
        //有可能k超出了链表的范围，导致走到末尾了，此时返回NULL
        while (k--) {
            if(!fast)
                return NULL;
            fast=fast->next;
        }
        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：
1、先计算链表的长度：len
2、再找到整数第 len - k 个即可

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* cur = pListHead;
        int len=0;
        while(cur)
        {
            cur = cur->next;
            ++len;
        }
        if(len<k)
            return NULL;
        int right = len - k;
        while(right--)
        {
            pListHead = pListHead->next;
        }
        return pListHead;
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

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

原题链接：合并两个有序链表.

方法一：归并
1、定义一个新的结点，L1链表与L2链表比较值的大小，小的放前面
2、当其中一个链表为空之后，需要将另外一个链表链接在新链表后面（防止没有检测完）

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        struct ListNode* newnode=NULL,*tail=NULL;
        while(l1&&l2)
        {
            if(l1->val<l2->val)
            {
                if(tail==NULL)
                {
                    newnode=tail=l1;
                }
                else
                {
                    tail->next=l1;
                    tail=l1;
                }
                l1=l1->next;
            }
            else
            {
                if(tail==NULL)
                {
                    newnode=tail=l2;
                }
                else
                {
                    tail->next=l2;
                    tail=l2;
                }
                l2=l2->next;
            }
        }
        if(l1)
            tail->next=l1;
        if(l2)
            tail->next=l2;
        return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

制作不易，记得点赞！！！