题意: 给出单链表的head指针, 要求去除链表中所有出现重复的元素, 如1->2->3->3->4->4->5, 返回 1->2->5

这题纠结了有两天,  重要的是把思路想清楚然后就可以痛苦的A掉, 不然老是会绕来绕去...

我的大体思路是这样的: 使用三个指针 pre保存链表中前一个没有出现重复的结点, p保存当前测试是否出现重复的结点, q用来测试p.

使用flag标记是否是第一次找到没有出现重复结点. 如果当前被测试的结点为空或者后面已经没有结点, 直接返回.

 

附上代码:

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         ListNode *p = head, *pre = head;13         int flag = 0;14         while (true) {15             if (p == NULL or p->next == NULL) {16                 return head;17             } else {18                 ListNode *q = p->next;19                 while (q!= NULL and q->val == p->val) {20                     q = q->next;21                 }22                 if (p->next == q) {23                     if (flag == 0) {24                         flag = 1;25                         head = p;26                     } else {27                         pre = p;28                     }29                 } else {30                     if (flag == 0) {31                         head = pre = q;32                     } else {33                         pre->next = q;34                     }35                 }36                 p = q;37             }38         }39         return head;40     }41 };