某大厂IT类面试题-删除链表奇数位结点

2021-08-26 11:04

我是你二爷

IP属地：上海

[转自程序员实用技能公众号]

关于链表的编程题，有很多，最常见的比如反转、合并排序、倒数第几个结点、中间结点、是否有环等等，难点的还有求环的长度等等，今天先讲一题easy的。

本题是某家大厂出的面试题，具体是第几面出的就不说了，重要的是我们要能当场写出来！

删除链表的奇数位结点，打印出剩余的链表结点。比如1->2->3->4->5，删除奇数位结点后，输出2->4。

乍一看，很简单，就是每次指向.next.next（后移2位）不就行了吗？......谁都知道啊。

No talking,show me your code!

假如你遇到了，怎么办？此处可以先思考1分钟。

我的思路：

人为new一个新结点（假设是preHead），放在最前面，指向链表的头结点（注意：此方法在链表的编程题中屡试不爽）
进入循环，把preHead.next.next赋值给preHead.next，使preHead.next指向它的后2位结点
把preHead.next赋值给preHead，使preHead往后移2位
当链表共有奇数个结点时（不包括自己new的那个），最后一次循环时，preHead指向NULL，此时需要退出循环
当链表共有偶数个结点时（不包括自己new的那个），最后一次循环时，preHead指向尾结点，preHead.next指向NULL，此时需要退出循环

具体代码如下：

package com.linkedlist;
/** * @Author you guess * @Date 2021/6/1 22:29 * @Version 1.0 * @Desc 删除链表奇数位结点 */public class DeleteOddNode {    public static void main(String[] args) {        DeleteOddNode main = new DeleteOddNode();
        ListNode listNode1 = new ListNode(1);        ListNode listNode2 = new ListNode(2);        ListNode listNode3 = new ListNode(3);        ListNode listNode4 = new ListNode(4);        ListNode listNode5 = new ListNode(5);        ListNode listNode6 = new ListNode(6);        ListNode listNode7 = new ListNode(7);
        listNode1.next = listNode2;        listNode2.next = listNode3;        listNode3.next = listNode4;        listNode4.next = listNode5;        listNode5.next = listNode6;//偶数个结点        listNode6.next = listNode7;//奇数个结点
        main.printListNode(listNode1);
        ListNode newHead = main.deleteNode(listNode1);        System.out.println("-----删除后-----");        main.printListNode(newHead);    }
    /**     * 删除的具体实现     * 人为new一个新的结点放在头结点的前面     *     * @param head 头结点     * @return     */    public ListNode deleteNode(ListNode head) {        if (head == null) {            return null;        }        ListNode preHead = new ListNode(0);//人为new一个新的结点放在头结点的前面        preHead.next = head;        ListNode old = preHead;//记录原始的位置        while (preHead.next != null) {//如果共有偶数个结点，最后一次循环时preHead为最后一个结点，此时退出            preHead.next = preHead.next.next;            preHead = preHead.next;            if (preHead == null)//如果共有奇数个结点，最后一次循环时preHead为NULL，此时退出                break;        }        return old.next;    }
    /**     * 从头打印链表     *     * @param head 头结点     */    public void printListNode(ListNode head) {        while (head != null) {            System.out.println(head.val);            head = head.next;        }    }}

package com.linkedlist;
/** * @Author you guess * @Date 2020/12/12 15:27 * @Version 1.0 * @Desc */public class ListNode {    int val;    com.linkedlist.ListNode next;
    ListNode() {    }
    ListNode(int val) {        this.val = val;    }
    ListNode(int val, com.linkedlist.ListNode next) {        this.val = val;        this.next = next;    }}

以下是单步调试的截图：

当链表是1->2->3->4->5->6，最后一次循环时：