面试题解答系列：数组与链表

LeetCode相关题目参考

1.两数之和

参考答案：

class Solution {
public int[] twoSum(int[] numbers, int target) {
int [] res = new int[2];
if(numbers==null||numbers.length<2)
return res;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i < numbers.length; i++){
if(!map.containsKey(target-numbers[i])){
map.put(numbers[i],i);
}else{
res[0]= map.get(target-numbers[i]);
res[1]= i;
break;
}
}
return res;
}
}
2.两数相加

参考答案：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
19.删除链表的倒数第N个节点

我的答案：（13ms）

public ListNode removeNthFromEnd(ListNode head, int n) {
// 正确性判断 if (null == head || null == head.next) {
return null;
}
int num = 0;
// 定义一个虚拟头结点方便遍历链表 ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode prev = dummyHead;
// 一次遍历找到链表的总数 while (null != prev.next) {
num++;
prev = prev.next;
}
// 二次遍历删除对应的节点 prev = dummyHead;
for (int i = 0; i < num - n; i++) {
prev = prev.next;
}// end for:找到了删除节点的前序节点 ListNode delNode = prev.next;
prev.next = prev.next.next;
delNode.next = null;
// 返回头结点 return dummyHead.next;
}
我的答案2：（16ms）

public ListNode removeNthFromEnd(ListNode head, int n) {
// 正确性判断 if (null == head || null == head.next) {
return null;
}
HashMap<Integer, ListNode> map = new HashMap<>();
// 定义一个虚拟头结点方便遍历链表 ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode prev = dummyHead;
map.put(0, dummyHead);
// 一次遍历，将序号与ListNode对应存入map中 for (int i = 1; null != prev.next; i++, prev = prev.next) {
map.put(i, prev.next);
}
// 删除对应的节点 int delNodeNum = map.size() - n;
ListNode delNode = map.get(delNodeNum);
prev = map.get(delNodeNum - 1);
prev.next = prev.next.next;
delNode.next = null;// help GC
// 返回头结点 return dummyHead.next;
}
参考答案：（26ms）

public ListNode removeNthFromEnd(ListNode head, int n) {
// 正确性判断 if (null == head || null == head.next) {
return null;
}
// 定义虚拟头结点方便遍历 ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
// 定义快慢两个节点 ListNode fast = dummyHead;
ListNode slow = dummyHead;
// 让fast先跑到第n个位置 for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// 再让两个一起移动，当fast为尾节点时slow的位置即删除元素的位置 while (null != fast) {
fast = fast.next;
slow = slow.next;
}
ListNode delNode = slow.next;
slow.next = slow.next.next;
delNode.next = null;// help GC.
return dummyHead.next;
}
21.合并两个有序链表（剑指Offer面试题25）

参考答案：（15ms）

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head = null;
if (l1.val < l2.val) {
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
74.搜索二维矩阵（剑指Offer面试题4）

参考答案：（8ms）

public boolean searchMatrix(int[][] matrix, int target) {
// 正确性判断 if (null == matrix || 0 == matrix.length) {
return false;
}
if (null == matrix[0] || 0 == matrix[0].length) {
return false;
}
int row = matrix.length;
int col = matrix[0].length;
int start = 0, end = row * col - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
int number = matrix[mid / col][mid % col];
if (number == target) {
return true;
} else if (number > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
141.环形链表

我的答案：（14ms）

public boolean hasCycle(ListNode head) {
// 正确条件判断 if (null == head || null == head.next) {
return false;
}
// 引入虚拟头结点 ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
HashMap<ListNode, Integer> map = new HashMap<>();
ListNode prev = dummyHead;
// 遍历链表 while (null != prev.next) {
if (map.containsKey(prev.next)) {
return true;
} else {
map.put(prev.next, prev.next.val);
prev = prev.next;
}
}
// 如果遍历到了链表尾巴都没找到则返回false return false;
}
参考答案：（3ms）

public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
// move 2 steps fast = fast.next.next;
// move 1 step slow = slow.next;
if(fast == slow)
return true;
}
return false;
}
147.对链表进行插入排序

图片描述(最多50字)

public ListNode insertionSortList(ListNode head) {
// 正确性判断 if (null == head || null == head.next) {
return head;
}
// 定义一个新的节点，这个节点的作用是一个一个把head开头的链表插入到dummy开头的链表里 ListNode dummy = new ListNode(-1);
// 类似于冒泡排序法的遍历整个链表 while (null != head) {
ListNode pre = dummy;
while (null != pre.next && pre.next.val < head.val) {
pre = pre.next;
}
ListNode temp = head.next;
head.next = pre.next;
pre.next = head;
head = temp;
}
return dummy.next;
}
148.排序链表

参考答案：（4ms）

public ListNode sortList(ListNode head) {
// 正确性判断 if (null == head || null == head.next) {
return head;
}
// 第一次遍历：找到链表长度 int len = 0;
ListNode cur = head;
while (null != cur) {
len++;
cur = cur.next;
}
// 第二次遍历：保存链表的值 int[] nums = new int[len];
cur = head;
for (int i = 0; i < len; i++) {
nums[i] = cur.val;
cur = cur.next;
}
// 第三次遍历：改变链表的值 Arrays.sort(nums);
cur = head;
for (int i = 0; i < len; i++) {
cur.val = nums[i];
cur = cur.next;
}
return head;
}
这里想吐槽一下：因为上面的算法遍历了三次链表，我想着使用ArrayList来少一次遍历结果发现运算速度达到了20ms左右…时间好像都花在了ArrayList转数组这个操作上了…这或许就是传说中的负优化吧…
203.删除链表中的节点（剑指Offer面试题18）

参考答案：

/**

• Definition for singly-linked list.
• public class ListNode { * int val;

• ListNode next;

• ListNode(int x) { val = x; }

• }
  */class Solution { public ListNode removeElements(ListNode head, int val) {
  // 定义一个虚拟头结点
  ListNode dummyHead = new ListNode(-1);
  dummyHead.next = head;
  ListNode prev = dummyHead;
  while (prev.next != null) {
  if (prev.next.val == val) {
  prev.next = prev.next.next;
  } else {
  prev = prev.next;
  }
  }
  return dummyHead.next;
  }
  }
  206.反转链表（剑指Offer面试题6、面试题24）

参考答案：（0ms）

public ListNode reverseList(ListNode head) {
ListNode pre = null;
while (null != head) {
ListNode temp = head;
head = head.next;
temp.next = pre;
pre = temp;
}
return pre;
}
442.数组中重复的数据（剑指Offer面试题3）

我的答案：（56ms）

public List findDuplicates(int[] nums) {
List result = new ArrayList<>();
// 正确性判断
if (null == nums || 0 == nums.length) {
return result;
}
// 创建一个HashMap，K值存位置，V值存数据
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// 如果存在重复的V值那么则有重复的元素存在
if (map.containsKey(nums[i])) {
result.add(nums[i]);
}
map.put(nums[i], i);
}
return result;
}
参考答案：（14ms）

public List findDuplicates(int[] nums) {
List res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
for (int i = 0; i < nums.length; i++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index] > 0) nums[index] *= -1;
else {
res.add(index + 1);
}
}
return res;
}

喜欢这篇文章的可以点个赞，欢迎大家留言评论，记得关注我，每天持续更新技术干货、职场趣事、海量面试资料等等
如果你对java技术很感兴趣也可以加入我的java学习群（374308445）来交流学习，里面都是同行，群验证【CSDN2】有资源共享。