首页 > 代码库 > 注意链表的尾部

注意链表的尾部

2024-07-11 21:11:31   217人阅读

今天做了Leetcode上面一道题Remove Duplicates from Sorted List II，要去去除链表中重复的节点，代码如下

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *deleteDuplicates(ListNode *head) {12         if(head==NULL||head->next==NULL)13         {14             return head;15         }16         ListNode *p=head,*prev=new ListNode(0),*head2=prev;17         int count=0;18         while(p->next!=NULL)19         {20             if(count==0&&p->val!=p->next->val)21             {22                 prev->next=p;23                 prev=p;24             }25             else if(p->val==p->next->val)26             {27                 count++;28             }29             else if(count>0)30             {31                 count=0; 32             }33             p=p->next;34         }35         if(count==0)36         {37             prev->next=p;38         }39        // else40        //{41        //     prev->next=NULL;42        //}43         head=head2->next;44         delete head2;45         return head;46     }47 };

注意到39-42行被注释掉的代码，注释掉，会怎么样？

分析一下算法，count表示前面与当前指针val相等的节点个数，对于末尾指针，前面如果没有与其数值相等，则加入链表，否则，则不加入链表，但是，如果末尾指针前面存在与其相等的数，是不是可以不用管它？不是的，因为是原地对链表操作，所以如果不处理的画，那么最后prev的next还是会指向另一个节点，而这个节点并不是我们想要的，所以39-42行必须将prev的next指向空指针。当然对于存在重复的节点，可以直接delete之，如果该节点是分配到堆上的话。


联系
我们