一、剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

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


struct ListNode* getKthFromEnd(struct ListNode* head, int k){
         struct ListNode*fast=head;
         struct ListNode*slow=head;
         if(head==NULL)
         {
             return NULL;
         }
         while(k--)
         {
             if(fast!=NULL)
             {
                fast=fast->next;
             }
             else
             {
                 return NULL;
             }
         }
         while(fast!=NULL)
         {
             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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

二、21. 合并两个有序链表

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

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

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


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
      struct ListNode*l1=list1;
      struct ListNode*l2=list2;
      struct ListNode*head=NULL;
      struct ListNode*tail=NULL;
      if(l1==NULL)
      {
          return l2;
      }
      if(l2==NULL)
      {
          return l1;
      }
      while(l1&&l2)
      {
          if(l1->val<l2->val)
          {
              if(tail==NULL)
              {
                  head=l1;
                  tail=l1;
              }
              else
              {
                  tail->next=l1;
                  tail=tail->next;
              }
              l1=l1->next;
          }
          else
          {
              if(tail==NULL)
              {
                  head=l2;
                  tail=l2;
              }
              else
              {
                  tail->next=l2;
                  tail=tail->next;
              }
              l2=l2->next;
          }
      }
      if(l1!=NULL)
      {
          tail->next=l1;
      }
      if(l2!=NULL)
      {
          tail->next=l2;
      }
      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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

三、206. 反转链表

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

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


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*cur=head;//头插法
    struct ListNode*newnode=NULL;
    while(cur!=NULL)
    {
        struct ListNode*next=cur->next;//将cur后一个节点存起来
          cur->next=newnode;//将cur头插新节点
          newnode=cur;
          cur=next;
    }
    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * 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*n1=NULL;//逆置链表
    struct ListNode*n2=head;
    struct ListNode*n3=head->next;
    while(n2!=NULL)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3!=NULL)
        {
          n3=n3->next;
        }
    }
    return n1;
}
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

四、203. 移除链表元素

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

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

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


struct ListNode* removeElements(struct ListNode* head, int val){
   if(head==NULL)
   {
       return NULL;
   }
   struct ListNode*cur=head;
   struct ListNode*prev=NULL;
   while(cur!=NULL)
   {
       if(head->val==val)//考虑头删
       {
           head=head->next;
           cur=head;
       }
      else
      {
          if(cur->val==val)//如果是在中间删或者尾删
          {
            prev->next=cur->next;
            cur=prev->next;
          }
          else
          {
              prev=cur;//如果不是就向后走
              cur=cur->next;
          }
      }
   }
   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