[关闭]
@Sarah 2016-01-03T19:08:33.000000Z 字数 3729 阅读 1349

Linked List

1 dummy node 能减少if语句
2

算法

面经去哪里看？

面试信息 www.themianjing.com 整理来自一亩三分地
更新glassdoor
carreup
mitbbs 可以用搜索引擎

C++面试不用看书 会一点基本语法就可以， 实在不会买薄的书 前几章看一看，一遍做题一边写，其实根本不用看书，遇到不会的用谷歌，边用边学学起来很快，只看书的话效率不高

前端一般会问什么：
30%JS之类的、web design，system design 但对new grad 问的挺少的
60%算法

~~~www.themianjing.com
一亩三分地
www.glassdoor.com 看interwiew
mitbbs.com 看jobhunting
careercup 有错的答案
http://www.collabedit.com/

mitbbs上东西特别多 用搜索功能来看

准备面试要两三个月 一遍准备一遍投简历，面试要分等级，做百分之70的题再去面试，第一轮面试涨经验，一般两遍做题，第二遍提高质量，至少不能有错。

一个月：基础薄弱：刷题4-6个小时 一个月差不多能刷完

实习 项目 开源项目 关键词

new一下相当于复制了一份到一个新的地方
list只是一个地址

1 dummy node 减少if :if多了难懂 也不容易写对
2linked list基本技巧
3 快慢指针

删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素每个元素只留下一个。
您在真实的面试中是否遇到过这个题？ Yes
样例
给出1->1->2->null，返回 1->2->null
给出1->1->2->3->3->null，返回 1->2->3->null

  1. public class Solution {
  2.     public ListNode deleteDuplicates(ListNode head) {
  3.         if (head == null) {
  4.             return null;
  5.         }
  7.         ListNode node = head;
  8.         while (node.next != null) {
  9.             if (node.val == node.next.val) {
  10.                 node.next = node.next.next;//删掉了
  11.             } else {
  12.                 node = node.next;
  13.             }
  14.         }
  15.         return head;
  16.     }
  17. }

命名不要用p1 p2之类的 难度

遍历list,如果发现和后面的一样，就把后面的那个删除掉
遍历每一个节点
只要发现我和我后面的一样 删除
进入下一个while
指针往下挪一个位置

删除排序链表中的重复数字 II

给定一个排序链表，删除所有重复的元素只留下原链表中没有重复的元素。
您在真实的面试中是否遇到过这个题？ Yes
样例
给出1->2->3->3->4->4->5->null，返回1->2->5->null
给出1->1->1->2->3->null，返回 2->3->null

  3. public class Solution {
  4.     public ListNode deleteDuplicates(ListNode head) {
  5.         if(head == null || head.next == null)
  6.             return head;
  8.         ListNode dummy = new ListNode(0);
  9.         dummy.next = head;
  10.         head = dummy;
  12.         while (head.next != null && head.next.next != null) {
  13.             if (head.next.val == head.next.next.val) {
  14.                 int val = head.next.val;
  15.                 while (head.next != null && head.next.val == val) {
  16.                     head.next = head.next.next;
  17.                 }            
  18.             } else {
  19.                 head = head.next;
  20.             }
  21.         }
  23.         return dummy.next;
  24.     }
  25. }

dummu node:原来的点之前的一个点
dummy 的next指向头
作用：当头不确定的时候，dummy指向头
这个题头如果出现了多次就没有了，头可能会被删掉，所以
dumy支持可变动的头

while走链表，如果下面两个点，比较后面两个点是否一样，一样的话删掉

list删除一个点的话,删除B，是把A.next = C,
删除B和B没关系，是把上一个点和下一个点连起来

首先保证head.next 和head.next.next这两个点存在

1删除：知道前一点才能删除
2访问点.next 一定保证点不等于空。先检查空再检查值
3dummy node 这个东西

做binary tree 的时候，访问点. 一定要有探空的条件

翻转链表

翻转一个链表
您在真实的面试中是否遇到过这个题？ Yes
样例
给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null
挑战
在原地一次翻转完成

比较频繁 不用dummy node 因为知道最后一个点是头
多画图 画清楚链表

  1. public class Solution {
  2.     /**
  3.      * @param head: The head of linked list.
  4.      * @return: The new head of reversed linked list.
  5.      */
  6.     public ListNode reverse(ListNode head) {
  7.         ListNode prev = null;
  8.         while (head != null) {
  9.             ListNode temp = head.next;//把head的next信息保存
  10.             head.next = prev;
  11.             prev = head;
  12.             head = temp;
  13.         }
  14.         return prev;
  15.     }
  16. }

prev head之前的位置
prev一开始 = 空，h 是头
p挪到h，h挪到next
进行交换

“谁写在等号右边，接下来这个东西就写在等号的左边”

翻转链表 II

翻转链表中第m个节点到第n个节点的部分
您在真实的面试中是否遇到过这个题？ Yes
样例
给出链表1->2->3->4->5->null， m = 2 和n = 4，返回1->4->3->2->5->null
注意
m，n满足1 ≤ m ≤ n ≤ 链表长度
挑战
在原地一次翻转完成

从m翻转到n 步骤
1找m前一点
2找m
3从pre m 和m反转（按第一题）
4把前后指针连好
把1.next指向4 把后面的指向5
5异常处理

  1. /**
  2.  * Definition for ListNode
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  * }
  7.  */
  8. public class Solution {
  9.     public ListNode reverseBetween(ListNode head, int m, int n) {
  10.         if (m >= n || head == null) {
  11.             return head;
  12.         }
  14.         ListNode dummy = new ListNode(0);
  15.         dummy.next = head;
  16.         head = dummy;//用dummy决定头
  18.         for (int i = 1; i < m; i++) {
  19.             if (head == null) {
  20.                 return null;
  21.             }
  22.             head = head.next;
  23.         }
  25.         ListNode premNode = head;
  26.         ListNode mNode = head.next;
  27.         ListNode nNode = mNode, postnNode = mNode.next;
  28.         for (int i = m; i < n; i++) {
  29.             if (postnNode == null) { //异常处理
  30.                 return null;
  31.             }
  32.             ListNode temp = postnNode.next;
  33.             postnNode.next = nNode;
  34.             nNode = postnNode;
  35.             postnNode = temp;
  36.         }
  37.         mNode.next = postnNode;//拼接
  38.         premNode.next = nNode;
  40.         return dummy.next;
  41.     }
  42. }

怎么知道是<还是<= ：把数带进去

Dummy Node

Scenario: When the head is not determinated
1. Remove Duplicates from Sorted List II 2. Reverse Linked List II
3. Merge Two Sorted Lists
4. Partition List

链表划分Partition List

给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。
你应该保留两部分内链表节点原有的相对顺序。
您在真实的面试中是否遇到过这个题？ Yes
样例
给定链表 1->4->3->2->5->2->null，并且 x=3
返回 1->2->2->4->3->5->null

  1. public class Solution {
  2.     public ListNode partition(ListNode head, int x) {
  3.         if (head == null) {
  4.             return null;
  5.         }
  7.         ListNode leftDummy = new ListNode(0);
  8.         ListNode rightDummy = new ListNode(0);
  9.         ListNode left = leftDummy, right = rightDummy;
  11.         while (head != null) {
  12.             if (head.val < x) {
  13.                 left.next = head;
  14.                 left = head;
  15.             } else {
  16.                 right.next = head;
  17.                 right = head;
  18.             }
  19.             head = head.next;
  20.         }
  22.         right.next = null;
  23.         left.next = rightDummy.next;
  24.         return leftDummy.next;
  25.     }
  26. }

3.1.2=48''

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注