C\C++刷题ADY3

题目来源：力扣

1.第一题

203. 移除链表元素 - 力扣（LeetCode）

思路分析:（不带哨兵位的头节点）

每次去分析一个节点，

如果节点不是存的是6，就拿节点来尾插

如果节点存的不是6，就把节点free掉

 思路分析：（带哨兵位的头节点）

带哨兵位的头节点的优势之一就是方便尾插

也就是说不需要判断开始尾插的时候是不是为NULL

不带哨兵位头节点需要判断第一插入的时候的节点是不是NULL，以此区分后续的尾插

PS：带哨兵位的思路请读者自己完成，尾插的思路并没有改变，变的仅仅是多了一个哨兵头节点，方便尾插

带哨兵位的头节点仅仅只是方便尾插，其余的操作还是不带哨兵位的头节点的单链表更舒服，实际和OJ题目中几乎不用带哨兵位的头节点（除非明确说明）

参考代码（不带哨兵位的头节点）：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur = head;
	struct ListNode* newhead;
    struct ListNode* tail;
	newhead = tail = NULL;
 
	while (cur)
	{
		if (cur->val != val)
		{
			if (tail == NULL)
			{
				newhead = tail = cur;
			}
			else
			{
				tail->next = cur;
				tail = tail->next;
			}
 
			cur = cur->next;
		}
		else
		{
			struct ListNode* next = cur->next;
			free(cur);
			cur = next;
		}
	}
    if(tail)
    {
        tail->next = NULL;
    }
	return newhead;
}

2.第二题

21. 合并两个有序链表 - 力扣（LeetCode）

 思路分析：

给一个head指针

给一个tail指针

取较小的尾插

参考代码1(不带哨兵位的头节点)：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
   if(list1==NULL)
        return list2;
   if(list2==NULL)
        return list1;
 
    struct ListNode* head;
    struct ListNode* tail;
    head=tail=NULL;
 
    //取小的尾插
    while(list1 && list2)
    {
        if(list1->val < list2->val)
        {
            if(tail == NULL)
            {
                head = tail = list1;
            }
        
            else
            {
            tail->next = list1;
            tail = tail->next;
            }
            list1 = list1->next;
        }
        else
        {
            if(tail == NULL)
            {
                head = tail = list2;
            }
        
            else
            {
            tail->next = list2;
            tail = tail->next;
            }
            list2 = list2->next;
        }
      
    }
      if(list1)
        tail->next = list1;
        if(list2)
        tail->next = list2;
 
        return head;
 
}

参考代码2(带哨兵位的头节点)：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
        struct ListNode*guard,*tail;
        guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
        guard->next = NULL;
 
        //取小的尾插
        while(list1 && list2)
        {
            if(list1->val<list2->val)
            {
                tail->next = list1;
                tail = tail->next;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
                list2 = list2->next;
            }
        }
        if(list1)
        {
            tail->next= list1;
        }
        if(list2)
        {
            tail->next=list2;
        }
 
    struct Node* head =guard->next;
    free(guard);
    return head;
 
}