单链表的简单习题

1.合并两个链表

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

屏幕截图 2022-01-20 150104

示例 1：

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

暴力法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//首先要创建一个头节点和一个用来链接两个链表的节点,让两个链表一个一个比较然后链接起来
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* HeadNode=(struct ListNode* )malloc(sizeof(struct ListNode));
    struct ListNode* pMove=HeadNode;
    while(list1&&list2){
        if(list1->val<=list2->val){
            pMove->next=list1;
            list1=list1->next;
        }else{
            pMove->next=list2;
            list2=list2->next;
        }
        pMove=pMove->next;
    }
    if(list1) pMove->next=list1;
    else pMove->next=list2;
    return HeadNode->next;
}

2.逆转链表

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

> 输入：head = [1,2] > 输出：[2,1]

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


struct ListNode* reverseList(struct ListNode* head){
      struct ListNode* pre=NULL;
      struct ListNode* cur=head;
      while(cur)
      {
          struct ListNode* next=cur->next;//链表只会保存下一个节点，当逆转的时候原来的下一个节点就会消失，所以必须有一个结构体指针记录下一个节点
          cur->next=pre;
          pre=cur;
          cur=next;
      }
      return pre;//逆转后原头节点变成了尾见点，原来的尾节点变成了头节点，因为pre一直记录的到cur尾NULL的时候，所以pre就是现在的尾节点。
}

以下是动图：

3. 删除链表中重复的节点

在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。

数据范围
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。

样例1
输入：1->2->3->3->4->4->5

输出：1->2->5
样例2
输入：1->1->1->2->3

输出：2->3

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 * 
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct ListNode* deleteDuplication(struct ListNode* head) {
    struct ListNode* pHead=(struct ListNode*)malloc(sizeof(struct ListNode));
    pHead->next=head;
    struct ListNode* pre=pHead;
    struct ListNode* cur=head;
    if(!head) return;
    while(cur)
    {
        while(cur&&pre->next->val==cur->val) cur=cur->next;
        if(pre->next->next==cur) pre=pre->next;
        else pre->next=cur;
    }
    return pHead->next;
}

warning:不能采用pre和cur都是首节点，然后开始判断的情况，因为会有这种特殊情况：从首节点开始到尾就是重复了