Delete the Kth Node In List

发表于 | 分类于

Delete List Node(删除链表中的第倒数第k个节点)

题目描述：

给定一个链表的第头节点，要求删除链表中的倒数第k个节点。

例子：

1->2->3->4->5->NULL.比如删除倒数第二个节点4，要求返回链表头节点包含1->2->3->5->NULL.

解题思路：

因为单项链表无法向前遍历的特点，所以我们可以用一个指示节点来帮助我们找到链表中的倒数第k个节点。做法是：先定义一个指向指针，从链表头结点开始遍历先走k步；而后再定义个遍历指针从链表头部开始遍历，当指示节点遍历到链表尾部的时候，这个时候后遍历的指针刚好达到链表中的第k个节点。需要注意的是，我们删除第k个节点，需要知道第k-1个节点的指针，所以要定义一个pre指针用来保存待删除节点的前一个节点。

代码如下：

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
class removeLastKthNode1{
public:
    ListNode* removeLastKthNode(ListNode* head, int lastKth){
        if (head == NULL || lastKth < 1)
            return head ;
        ListNode* cur = head;
        while(cur != NULL){
            cur = cur->next;
            lastKth--;
        }     // 先走k步的指示指针
        if (lastKth == 0) {
            return head->next;
            // k的大小大于链表长度的情况
        }
        if (lastKth < 0){
            cur = head;
            while (lastKth != -1){
                cur = cur->next;
                lastKth++;
            }
            cur->next = cur->next->next;
        }    // 删除找到的节点
        return head;
    }
};

延伸题目1:

链表中的中间节点。与上面的思路一样，利用快慢指针的方法就可以找到链表的中间节点。首先定义快指针fast和慢指针slow，快指针每次走两步，慢指针一次走一步。这样当快指针到达链表末尾的时候，慢指针刚好到达链表的中间节点部分。同样记得记录待删除节点的前一个节点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class removeMidNode1{
public:
    ListNode* removeMidNode(ListNode* head){
        if (head == NULL || head->next == NULL)
            return head;
        if (head->next->next == NULL)
            return head->next;
        ListNode* slow = head;
        ListNode* fast = head->next->next;//定义快慢指针
        while(fast->next != NULL && fast->next->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }                                 //找到链表的中间节点
        slow->next = slow->next->next;
        return head;
    }
};

延伸题目2:

给定一个链表的头节点和整数a和整数b。要求删除链表中a/b地方的节点。这一题的主要麻烦之处是找到要删除的节点在链表中的位置，所以a/b在链表中的位置该怎么找事关键。这边主要用到的是(a*n)/b公式，得到的数值即为要删除节点在链表中的位置。

代码如下:

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
class removeByRation1{
public:
    ListNode* removeByRation(ListNode* head, int a, int b){
        if (a < 0 || a > b)
            return head;
        int n = 0;
        ListNode* cur = head;
        while(cur != NULL){
            cur = cur->next;
            n++;
        }            // 计算链表的长度
        int kth = int(ceil(double(a * n) / double(b)));
                   // 找到链表的位置
        if (kth == 1)
            return head->next;  //如果是头节点的情况
        if (kth > 1) {
            cur = head;
            while (--kth != 1) {
                cur = cur->next;
            }
            cur->next = cur->next->next;
        }
        return head;
    }
};