如何使用 哑节点（dummy node），高效解决问题

目录

前言：

1.19. 删除链表的倒数第 N 个结点

 2.24. 两两交换链表中的节点

3.82. 删除排序链表中的重复元素 II

---

前言：

在对链表进行 *** 作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了，可省去许多麻烦。

1.19. 删除链表的倒数第 N 个结点

问题描述：

思路：

先求出链表长度，后找到要被删除节点的前一个节点。第二次遍历是是从哑巴节点开始的。

代码：

int getLength(struct ListNode* head) {
    int length = 0;
    while (head) {
        ++length;
        head = head->next;
    }
    return length;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));//创建哑巴节点
    dummy->val = 0, dummy->next = head;
    int length = getLength(head);//求出链表长度
    struct ListNode* cur = dummy;
    int k=length-n;
    while(k--)//找到要被删除节点的前一个节点
    {
       cur=cur->next;
    }
    cur->next = cur->next->next;
    return dummy->next
}

 2.24. 两两交换链表中的节点

 描述：

 思路：

创建哑结点 dummyHead，令 dummyHead->next = head。cur 表示当前到达的节点，初始时 cur = dummyHead。每次需要交换 cur后面的两个节点.

若cur后面存在两个节点，将两个节点设为 node1 和 node2。

cur -> node1 -> node2变为---- cur->node2 -> node1，再将cur置为node1。再重复以上 *** 作

代码：

struct ListNode* swapPairs(struct ListNode* head){
    if(head==NULL||head->next==NULL)
    {
       return head;
    }
    struct ListNode*dummyHead=(struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->next=head;
    struct ListNode*cur=dummyHead;
     while(cur->next&&cur->next->next)
     { 
         struct ListNode* Node1 = cur->next;
         struct ListNode* Node2 =cur->next->next;
         cur->next=Node2;
         Node1->next=Node2->next;
         Node2->next=Node1;
         cur=Node1;
     }
     return dummyHead->next;
}

3.82. 删除排序链表中的重复元素 II

思路：

由于链表的头节点可能会被删除，因此我们需要额外使用一个哑节点（dummy node）指向链表的头节点。初始时，令cur=dummy node。如果cur后面两个节点的值相同(记为A)，cur的next指向下个节点，直到cur->next节点的值不为A。如果cur后面连续两个节点的值不同，cur往后遍历

如图：

代码：

struct ListNode* deleteDuplicates(struct ListNode* head)
 {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* cur = dummy;
    while (cur->next && cur->next->next)
     {
        if (cur->next->val == cur->next->next->val)//如果cur后面两个节点的值相同，cur的next指向下个节点
         {
            int x = cur->next->val;
            while (cur->next && cur->next->val == x)
             {
                cur->next = cur->next->next;
            }
        }
         else 
        {
            cur = cur->next;//cur后面连续两个节点的值不同，cur往后遍历
        }
    }
    return dummy->next;
}

通过这三个题目练习，可以更好的运用哑节点处理头节点要变更的题目