【链表】打卡4：删除单链表的中间结点

发表于 | 更新于 | 分类于 > | 次阅读
删除单链表的中间结点

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢。

【题目描述】

给定链表的头结点head，实现删除链表的中间结点的函数。

　　例如：

　　步删除任何结点；

　　1->2，删除结点1；

　　1->2->3，删除结点2；

　　1->2->3->4，删除结点2；

　　1->2->3->4-5，删除结点3；

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)

【难度】

士：★☆☆☆

解答

自己思路

删除中间结点，使用一个数存储链表中间结点的计数。而这个数计算方法如下：如果长度是偶数，就除以2；如果是奇数，就除以2加1。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static Node deleteMidNode(Node head){
	if(head == null || head.next == null){
		return head;
	}
    int length = 0;
    Node node = head;
    while(node != null){
        length++;
        node = node.next;
    }
    int mid = length % 2 == 0 ? length/2 : length/2+1; 
    node = head;
    int i = 0;
    while(++i <= mid-1){
        node = node.next;
    }
    if(mid == 1){
        return head.next;
    }else{
        node.next = node.next.next;
        return head;
    }
}

作者思路

这道题要求删除中间结点，我们可以采用双指针的方法来做，就是用一个快指针和一个慢指针，快指针每次前进两个结点，而慢指针每次前进一个结点。当快指针遍历完结点时，慢指针刚好就在中间结点了。之前写过一篇一些常用的算法技巧总结也有所过指针使用的一些技巧。

不过在做的时候，最好是先把一些特殊情况先处理好，例如删除的可能是第一个结点，也有可能不用删除结点(只有一个结点时就不用删除了。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static Node removeMidNode(Node head) {
    if(head == null || head.next == null)
        return head;
    if (head.next.next == null) { //只有两个结点时
        return head.next;
    }
    Node fast = head.next.next;//快指针
    Node slow = head;//慢指针

    //slow最终指向中间结点的前驱
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    //进行删除
    slow.next = slow.next.next;
    return head;
}

算法图片

上次那道删除倒数第 K 个结点的题（【链表问题】删除单链表中的第K个结点） 其实也是可以使用双指针的，但个人认为，那道题使用双指针的方法并没有我上次那个做法优雅，而这次删除中间结点，则用双指针比较优雅。至于原因，可以自己打下代码看看。

之所以说这个事，是因为有人跟我提双指针的建议，我是非常欢迎有人给我提建议的，不过你的建议如何。不过一上来就说我那篇文章太敷衍，我也是醉了。我开头已经说了，只提供简单的解答，而且也把刷题的文章放到次条了。

问题拓展

题目：删除链表中 a / b 处的结点

【题目描述】

　　给定链表的头结点 head、整数 a 和 b，实现删除位于 a/b 处结点的函数。

　　例如：

　　链表：1->2->3->4->5，假设 a/b 的值为 r。

　　如果 r = 0，不删除任何结点；

　　如果 r 在区间 (0,1/5] 上，删除结点 1；

　　如果 r 在区间 (1/5,2/5] 上，删除结点 2；

　　如果 r 在区间 (2/5,3/5] 上，删除结点 3；

　　如果 r 在区间 (3/5,4/5] 上，删除结点 4；

　　如果 r 在区间 (4/5,1] 上，删除结点 5；

　　如果 r 大于 1，不删除任何结点。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(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
/**删除链表中 a / b 处的结点
  * 这道题可以转换为删除第k=(a*n/b)个结点(公式如何得出？)
  * 其中n表示链表结点的个数，但由于(a*n/b)有可能出现小数，所以我们取K的上限。
  * 所谓上限就是大于等于k的最小整数
  */
public static Node removebyRatio(Node head,int a,int b){
    if(a<1 || a>b){
        return head;
    }
    int len = 0;//记录链表的长度
    Node node = head;
    while(node!=null){
        len++;
        node = node.next;
    }
    //问题转换为删除第k=(a*n/b)个结点
    int k = (int)Math.ceil((double)(a*len)/(double)b);
    if(k>1){
        node = head;
        //定位第K个结点的前继
        while(--k != 1){//只需要循环k-2次
            node = node.next;
        }
        node.next = node.next.next;
        return head;
    }
    if(k == 1){
        return head.next;
    }
    return head;
}

来源：苦逼的码农（ID:di201805）

（完）
谢谢你请我吃糖果！
0%