[转帖]BAT经典算法笔试题:逆转单向链表_招聘求职_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  生活服务区 »  招聘求职 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 2635 | 回复: 0   主题: [转帖]BAT经典算法笔试题:逆转单向链表        上一篇   下一篇 
    本主题由 Administrator 于 2019-9-6 7:29:30 移动
liuliying930406
注册用户
等级:中校
经验:2027
发帖:210
精华:0
注册:2018-10-9
状态:离线
发送短消息息给liuliying930406 加好友    发送短消息息给liuliying930406 发消息
发表于: IP:您无权察看 2019-1-24 15:03:52 | [全部帖] [楼主帖] 楼主


本文转自公众号潘旭网


不善言谈的优秀程序员在面试中往往是要吃巨亏的,你没有办法通过说话来轻易证明自己的实力。不论是大厂还是小厂,大部分面试官都不具备优秀的面试能力,它们也只能通过三言两语观察一下面试者的表面工夫。有很多这样吃了亏的程序员,不喜欢准备面试,不喜欢吹嘘虚假的不存在的经验和能力,甚至连网上的笔试题都懒得做,因为在实际工作中这些鸟题根本一点都用不上。

但是这并不是什么值得骄傲的真诚,面试不做准备是对目标企业的不尊重,也是个人性格上自大的一种表现。虽然所有的面试官都希望面试者是真实的无虚假的不做表面文章的,但是这样的人真的站在你面前时,几乎所有的面试官往往又都看不上。

那如何在尽量少做表面功夫的基础上让面试官能够看上你?其中的方法之一就是展现平时个人优秀的作品和实现代码,但是这需要时间需要实打实的功夫,能够有机会作出优秀个人作品的人并不多见,大多数人都在忙碌的工作中耗尽了所有的时间。那还有一个方法就是在笔试阶段大显身手,让自己优秀的代码能力跃然纸上,让面试官瞬间对你产生不一样的感觉。

不要被笔试阶段那些算法题给吼到了,在你眼里似乎它们是为程序天才们准备的。其实大多数公司的笔试题也是来源于网上,那些被无数人做烂的题目。你被题目搞晕了而别人没有,那是因为别人已经做过这道题了,而不是智商所致。

今天我要讲的算法题—— 逆转单向链表,它是一个非常简单的题目,但是如果你是第一次见到这道题,将它完完整整没有bug 的写出来是着实需要费一番功夫的。期望在那短短的笔试题环节就轻松搞定这道题,那真是非常有算法天赋的人才能做到的事。难道大厂里面的程序员个个都是天才,鬼才相信。天才总是极少数的,多数都是像老钱这样的庸才。

好,言归正传,下面我们开始讲解今天的算法题—— 逆转单向链表。首先这是一个单向的链表,不同于Java 里面的LinkedList,它是双向的链表。链表中每个节点之间通过next 指针串接起来,会有一个链表头和链表尾指针hold 住整个链表。逆转的任务就是将head -> a -> b -> c -> d <- tail 变成head -> d -> c -> b -> a <- tail。

BAT经典算法笔试题:逆转单向链表

链表结构表示

BAT经典算法笔试题:逆转单向链表

class Node<T> {
       T value;
       Node<T> next;
       Node(T value) {
              this.value = value;
       }
}
class ReverseLinkedList<T> {
 Node<T> head, tail;
}


链表构造器

我们需要将所有的元素一个一个的使用next 指针串接起来,链表的头尾节点要用head 和tail 变量把持住。加入新元素时,需要调整尾部节点的next 指针,指向新加入的元素节点。

BAT经典算法笔试题:逆转单向链表

class ReverseLinkedList<T> {
 private Node<T> head, tail;
 
 public ReverseLinkedList(T... values) {
       for (T value : values) {
              if (tail == null) {
 // 第一个节点
                     head = tail = new Node<>(value);
              } else {
 // 后面的节点往链表尾部追加
                     Node<T> oldTail = tail;
                     oldTail.next = tail = new Node<>(value);
              }
       }
 }
}
ReverseLinkedList<Integer> l = new ReverseLinkedList<>(1,2,3,4,5,6);


链表内容呈现

我们需要提供一个链表的输出方法,以便快速对比逆转后链表的内容是否正确

BAT经典算法笔试题:逆转单向链表

class ReverseLinkedList<T> {
 private Node<T> head, tail;
 public String toString() {
       StringBuilder sb = new StringBuilder();
       sb.append('[');
       Node<T> cur = head;
       while (cur != null) {
              sb.append(cur.value);
              cur = cur.next;
              if (cur != null) {
                     sb.append(',');
              }
       }
       sb.append(']');
       return sb.toString();
 }
}


迭代逆转算法

循环调整next 指针是最容易想到的方法,但是要将指针精确地逆转正确其实并不容易。下面代码中的循环部分很短,但是却很精致,使用了三个临时局部变量cur、next 和nextnext,稍有不慎就会出错。

BAT经典算法笔试题:逆转单向链表

当我写完下面这段代码时,虽然可以正常运行出期望的结果,但是总当心哪里会有遗漏,是不是什么地方少了个if else,这就是编写算法代码时常见的心理状态。class ReverseLinkedList<T> {

 private Node<T> head, tail
 
 public ReverseLinkedList<T> reverseByLoop() {
 // 空链表或者单元素都无需处理
       if (head == tail) {
              return this;
       }
       Node<T> cur = head;
       Node<T> next = cur.next;
       while (next != null) {
              Node<T> nextnext = next.next;
              next.next = cur;
              cur = next;
              next = nextnext;
       }
       tail = head;
       tail.next = null;
       head = cur;
       return this;
 }
}


递归逆转算法

使用递归的思想来解决这个问题也是一个很好的主意,只不过当链表特别长时,调用栈会很深,链表长到一定程度就会抛出臭名昭著的异常StackOverflowException。

BAT经典算法笔试题:逆转单向链表

class ReverseLinkedList<T> {
 private Node<T> head, tail
 public ReverseLinkedList<T> reverseByRecursive() {
       Node<T> oldTail = tail;
       tail = reverseFrom(head);
       tail.next = null;
       head = oldTail;
       return this;
 }
 private Node<T> reverseFrom(Node<T> from) {
      if (from == tail) {
        return from;
       }
       Node<T> end = reverseFrom(from.next);
       end.next = from;
       return from;
 }
}


完整代码

package leetcode;
public class ReverseLinkedList<T> {
       static class Node<T> {
              T value;
              Node<T> next;
              Node(T value) {
                     this.value = value;
              }
       }
       Node<T> head;
       Node<T> tail;
       @SafeVarargs
       public ReverseLinkedList(T... values) {
              for (T value : values) {
                     if (tail == null) {
                            head = tail = forNode(value);
                     } else {
                            Node<T> oldTail = tail;
                            oldTail.next = tail = forNode(value);
                     }
              }
       }
       public ReverseLinkedList<T> reverseByLoop() {
              if (head == tail) {
                     return this;
              }
              Node<T> cur = head;
              Node<T> next = cur.next;
              while (next != null) {
                     Node<T> nextnext = next.next;
                     next.next = cur;
                     cur = next;
                     next = nextnext;
              }
              tail = head;
              tail.next = null;
              head = cur;
              return this;
       }
       public ReverseLinkedList<T> reverseByRecursive() {
              Node<T> oldTail = tail;
              tail = reverseFrom(head);
              tail.next = null;
              head = oldTail;
              return this;
       }
       private Node<T> reverseFrom(Node<T> from) {
              if (from == tail) {
                     return from;
              }
              Node<T> end = reverseFrom(from.next);
              end.next = from;
              return from;
       }
       public String toString() {
              StringBuilder sb = new StringBuilder();
              sb.append('[');
              Node<T> cur = head;
              while (cur != null) {
                     sb.append(cur.value);
                     cur = cur.next;
                     if (cur != null) {
                            sb.append(',');
                     }
              }
              sb.append(']');
              return sb.toString();
       }
       private static <T> Node<T> forNode(T value) {
              return new Node<>(value);
       }
       public static void main(String[] args) {
              ReverseLinkedList<Integer> rl = new ReverseLinkedList<>(1, 2, 3, 4, 5, 6);
              System.out.println(rl.reverseByRecursive().reverseByRecursive());
       }
}


该贴由system转至本版2019-9-6 7:29:29



赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册