问题:
去除有序链表中重复的节点。
Example 1: Input: head = [1,1,2] Output: [1,2] Example 2: Input: head = [1,1,2,3,3] Output: [1,2,3] Constraints: The number of nodes in the list is in the range [0, 300]. -100 <= Node.val <= 100 The list is guaranteed to be sorted in ascending order.
解法:slow-fast pointers(快慢指针法)
- 0~i:满足题意的链表。
- j:探索是否当前节点满足题意(非重复):nums[j]!=nums[i](最后一个满足元素)
- 若满足:交换 j 和第一个不满足元素 i->next
- swap(i->next, j)
- i=i->next
- 继续探索下一个 j=j->next
代码参考:
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode() : val(0), next(nullptr) {} 7 * ListNode(int x) : val(x), next(nullptr) {} 8 * ListNode(int x, ListNode *next) : val(x), next(next) {} 9 * }; 10 */ 11 class Solution { 12 public: 13 ListNode* deleteDuplicates(ListNode* head) { 14 if(!head) return head; 15 ListNode* i=head, *j=head->next; 16 while(j) { 17 if(i->val != j->val) { 18 swap(i->next->val, j->val); 19 i=i->next; 20 } 21 j=j->next; 22 } 23 i->next=nullptr; 24 return head; 25 } 26 };