应届生求职招聘论坛

标题: 某大厂IT类面试题-删除链表奇数位结点 [打印本页]

作者: 我是你二爷 时间: 2021-8-26 11:04
标题: 某大厂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，最后一次循环时：

输出：

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

输出：

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

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

欢迎光临应届生求职招聘论坛 (https://bbs.yingjiesheng.com/)