链表OJ题

移除链表元素

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

 

方法一：【三指针--无哨兵位】

时间复杂度：O(N)

思想：

三个指针，cur负责对比val，tmp负责存储删除元素的下一个元素地址，prve负责存储删除元素的上一个元素地址。

易错：

• 记住prve是cur的前一个元素，那么它从NULL开始
• 循环条件
• 记得处理头节点和尾节点
• 造成野指针的错误❌

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

方法二：【双指针---无哨兵位】

struct ListNode* removeElements(struct ListNode* head, int val) 
{
       struct ListNode*newhead=NULL;
       struct ListNode*tail=NULL;
       struct ListNode*cur=head;
       while(cur)
       {
           //不是val的节点取下来尾插。
           if(cur->val != val)
           {
               //尾插
               if(tail == NULL)
               {
                   newhead=tail=cur;
               }
               else
               {
                   tail->next=cur;
                   tail=tail->next;
               }
               cur=cur->next;
           }
           else
           {
               struct ListNode*tmp=cur->next;
               free(cur);
               cur=tmp;
           }
           if(tail)
           {
               tail->next=NULL;
           }
       } 
       return newhead;          
}

方法三：【双指针---有哨兵位】

不带哨兵位：plist指向NULL

带哨兵位：plist指向头节点。这个节点不存储有效数据。

 

哨兵位的优势：如果有哨兵位就不需要二级指针了。带哨兵位的更简单。但在实践中和OJ中一般都是不带哨兵位的。 

不需要再判断链表是否为空了

struct ListNode* removeElements(struct ListNode* head, int val) 
{
    struct ListNode* cur=head;
    struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tail=newhead;
    //tail不为空。
    while(cur)
    {
        if(cur->val != val)
        {
            //这里不需要判断链表是否为空了，因为tail不可能为空。
            tail->next=cur;
            tail=tail->next;
            cur=cur->next;
        }
        else
        {
            struct ListNode* tmp=cur->next;
            free(cur);
            cur=tmp;
        }
    }
    //处理尾
    if(tail)
    {
        tail->next=NULL;
    }
    //这里要记得释放newhead
    struct ListNode*tmp=newhead;
    newhead=newhead->next;
    free(tmp);
    tmp=NULL;
    
    return newhead;
}

分割链表

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。OJ链接

这道题我们不建议使用不带哨兵位的方法，因为不带哨兵位的话我们就需要在两个链表连接的时候，判断两个链表是否为空的情况，比较麻烦。 

【易错点】

以上测试用例我们可以看到，9是链表中的最后一个数字，9指向NULL，所以代码最后写成

tail->next = list2->next;
free(list1);
free(list2);
 
return PHead;

这样是没错的，但是如果用例如下， 9的next指向1，形成了一个闭环，那么这样就会出错。所以我们要把tail2->next = NULL;

 

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//用不带头节点来写，两个链表都可能为NULL，都要判断非常麻烦
//所以我们用带头节点来写
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* list1=(ListNode*)malloc(sizeof(ListNode));
        ListNode* list2=(ListNode*)malloc(sizeof(ListNode));
        ListNode* tail1=list1;
        ListNode* tail2=list2;
        ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val < x)
            {
                tail1->next=cur;
                tail1=tail1->next;
            }
            else//cur->val >= x
            {
                tail2->next=cur;
                tail2=tail2->next;
            }
            cur=cur->next;
        }
        //尾巴处理
        tail1->next=list2->next;
        tail2->next=NULL;//易错
 
        PHead = list1->next;
        free(list1);
        free(list2);
        return PHead;
 
        //return list1->next;
    }
};

 反转链表

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

法一：【三指针】

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)//易错
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        n3=n3->next;
    }
    return n1;//易错
}

 要注意结束条件是n3==NULL！！

法二：【头插】

struct ListNode* reverseList(struct ListNode* head) {
	struct ListNode* cur = head;
	struct ListNode* newhead = NULL;
 
	while (cur)
	{
		struct ListNode* next = cur->next;
		//头插
		cur->next = newhead;
		newhead = cur;
 
		cur = next;
	}
 
	return newhead;
}

链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点 OJ链接

示例1：输入：1,{1,2,3,4,5}

返回值：{5}

示例2：输入：6,{1,2,3,4,5}

返回值：{}

---

思路：这个题我们可以通过控制fast和slow的间隔，来输出倒数第k个值。如果fast先走k步，然后两个再一起走，那么等到fast==NULL的时候，slow的值就是倒数第k个值。 如果fast先走k-1步，然后两个再一起走，那么等到fast->next==NULL的时候，slow的值就是倒数第k个值。

 k步 

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode*fast=pListHead;
    struct ListNode*slow=pListHead;
 
    while(k--)//走k
    {
        if(fast == NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
 
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

k-1步

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode*fast=pListHead;
    struct ListNode*slow=pListHead;
 
    while(--k)//走k-1
    {
        if(fast == NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
 
    while(fast->next)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

 

合并链表

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

 

• 取小尾插

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* tail=NULL,*head = NULL;
 
    if(list1 == NULL)
    return list2;
    if(list2 == NULL)
    return list1;
 
    while(list1 && list2)
    {
        if(list1->val < list2->val)
        {
            if(tail == NULL)
            {
                head=tail=list1;//易错
            }
            else
            {
                tail->next=list1;//已经放进去//易错
                tail=tail->next;//tail是尾节点，可以往后移动了
            }
            list1=list1->next;
        }
        else
        {
            if(tail == NULL)
            {
                head=tail=list2;//易错
            }
            else
            {
                tail->next=list2;//已经放进去//易错
                tail=tail->next;//tail是尾节点，可以往后移动了
            }
            list2=list2->next;
        }
    }
    if(list1)
    {
        tail->next=list1;
    }
    else
    {
       tail->next=list2;//已经不用在往后走了
    }
    return head;
}