剑指offer - 删除链表的节点

发表于 | 更新于

题意

在O(1)时间内删除链表节点。

题解

由于要删除一个节点，需要知道上一个节点的地址，将上一个节点的地址的next指向要删除节点的next。
但是，如果我们不改变next值，而是将要删除节点的下个节点中的值复制到当前节点，然后删除下个几点，相当于间接删除掉了这个节点。
注意几点：
如果是尾节点，还是需要从头遍历到尾删除的。
如果只有一个节点删除后要返回NULL。

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
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {}
};
class Solution {
public:
    ListNode* deleteNode(ListNode* pHead,ListNode *node)
    {
        if(pHead==NULL) return NULL;
        if(pHead==NULL) return pHead;
        if(node->next==NULL){ //尾节点
            ListNode * p= pHead,*pre=NULL;
            while(p->next){
                pre = p;
                p=p->next;
            }
            if(pre==NULL) return NULL;  //只有一个节点
            pre->next = NULL;
        }else{
            node->val=node->next->val;
            node->next=node->next->next;
        }
        return pHead;
    }
};

扩展题目

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。

题解

比较恶心。
需要考虑各种情况。
有序的数列，记录相邻的重复的数的个数，为1，则加到链表中，否则不管。注意开头和结尾。

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
40
41
42
43
44
45
46
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->next,*preSignal = NULL;
        if(cur==NULL) return pHead;//只有一个节点
        int num = pHead->val,numCount=1;
        do{
            if(num!=cur->val){
                if(numCount==1){
                    if(preSignal==NULL){
                        preSignal = pre;
                        pHead = preSignal;
                    }
                    else{
                        preSignal->next = pre;
                        preSignal = pre;
                    }
                }
                num=cur->val;
                numCount=1;
            }else{
                numCount++;
            }
            pre = cur;
            cur=cur->next;
        }while(cur);
        if(preSignal==NULL){
            if(numCount==1) //最后一个数不重复
                return pre;
            return NULL; //所有都重复
        }
        if(numCount==1)
            preSignal->next = pre;
        else
            preSignal->next = NULL;
        return pHead;
    }
};