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

我是你二爷

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

关于链表的编程题，有很多，最常见的比如反转、合并排序、倒数第几个结点、中间结点、是否有环等等，难点的还有求环的长度等等，今天先讲一题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，最后一次循环时：

输出：

2

4

6

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

输出：

2

4

6

如果链表只有1个或2个结点，以上代码也能正确输出。

当然，也有不new结点的方法或者其他更好的方法。