链表删除类题目总结

Posted on | In

上午刷题时，之前一道很简单的题写第二遍时卡住了。。。看来还是没理解透彻，题目为剑指Offer（五十六）：删除链表中重复的结点。

心得：

  • 先考虑一般情况1->2->3->3->4->4->5 处理后为 1->2->5；
  • 再考虑要删除的是第一个结点的情况（需要移动头节点）1->1->2->3->3->5 处理后为 2->5;
  • 最后考虑遍历到最后指针为空的情况，1->1->1->1 处理后为 {}。

coding就是一个思路转化成代码的过程，逻辑要清晰，善于用三种逻辑语句，卡在都想用pre = cur;cur = aft;语句来继续遍历，但如果删除重复后其实pre是不用移动的，遂if else考虑后清晰很多，if(删除重复)用cur = aft->next;，else。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead == NULL) return NULL;
        ListNode* pre = pHead, *cur = pHead, *aft = NULL;
        while(cur){
            aft = cur->next;
            if(cur->next != NULL && cur->val == cur->next->val){
                aft = cur->next;
                while(aft->next != NULL && aft->next->val == cur->val)
                    aft = aft->next;
                //处理cur在第一个结点时,前面已有cur->next->val判断重复
                if(cur == pHead)
                    pHead = aft->next;
                else//既然pre在第一个结点重复时不能向后指，加到else里
                    //全重复需要pHead为空，前面在aft->next为空停下，所以要aft最后定位前移一下
                    pre->next = aft->next;
                cur = aft->next;
            }
            //既然在有重复时pre不需移动，那就分两种情况向后遍历
            else{
                pre = cur;
                cur = cur->next;
            }
        }
        return pHead;
            
    }
};

类比删除值为x的元素

printList函数见(https://mintlucas.github.io/2019/02/26/C-%E7%AE%80%E6%B4%81%E7%9A%84%E9%93%BE%E8%A1%A8%E5%88%9B%E5%BB%BA/)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void deleteX(ListNode* &head, int x){
    if(head == NULL) return;
    ListNode* pre = head, *cur = head;
    while(cur){
        if(cur->val == x){
            if(cur == head){
                cur = cur->next;
                head = cur;
                pre = cur;
            }
            else{
                pre->next = cur->next;
                cur = cur->next;
            }
        }
        else{
            pre = cur;
            cur = cur->next;
        }
    }
}