Interview-Notes

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ // 排序，归并排序 class Solution { // 归并排序注意中点的划分 public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode fast = head.next; ListNode slow = head; while ( fast!= null && fast.next != null ) { fast = fast.next.next; slow = slow.next; } ListNode tmp = slow.next; slow.next = null; ListNode left = sortList(head); ListNode right = sortList(tmp); ListNode dummy = new ListNode(-100001); ListNode res = dummy; while (left != null && right != null) { if (left.val <= right.val) { res.next = left; left = left.next; } else { res.next = right; right = right.next; } res = res.next; } res.next = left == null ? right : left; return dummy.next; } }

哈希表 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //先存储A链表的所有结点，在遍历B链表。所以空间复杂度来到了O(m),A有m个节点的话 Set<ListNode> visited = new HashSet<ListNode>(); ListNode temp = headA; while (temp != null) { visited.add(temp); temp = temp.next; } temp = headB; while (temp != null) { if (visited.contains(temp)) { return temp; } temp = temp.next; } return null; } } 双指针 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode pA = headA, pB = headB; while (pA != pB) { pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; } }

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { // 思路：1. 得出链表的长度，然后走size - n - 1,接着进行删除 // 2. 快慢指针，让快指针先走n步，之后慢指针再出发， // 当快指针走到结尾的时候，慢指针指向的就是倒数第n个节点的前一个节点 public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1,head); ListNode fast = dummy; ListNode low = dummy; int count = 0; while (fast.next != null) { // fast走到最后一个节点需要停下来 fast = fast.next; count++; if (count >= n + 1) { low = low.next; } } low.next = low.next.next; return dummy.next; // int size = 1; // ListNode cur = head; // while (cur.next != null) { // cur = cur.next; // size++; // } // if (n == size) return head.next; // 特判 n == size 的情况 // cur = head; // for (int i = 1; i < size - n; i++) { // cur = cur.next; // } // cur.next = cur.next.next; // return head; } }

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { // 用一个变量记录进位 // public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyRes = new ListNode(); ListNode cur = dummyRes; int yushu = 0, sum = 0; while (l1 != null || l2 != null) { cur.next = new ListNode(); int var1 = (l1 == null) ? 0 : l1.val; int var2 = (l2 == null) ? 0 : l2.val; sum = var1 + var2 + yushu; cur.next = new ListNode(sum % 10); cur = cur.next; yushu = sum / 10; if (l1 != null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } } if (yushu != 0) { cur.next = new ListNode(yushu); } return dummyRes.next; } }

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { // 链表的题往往使用虚拟头结点的方法 ListNode dummy 让虚拟头结点指向head，避免对head特判 // 链表的题删除链表、翻转节点、添加节点都要用双指针 public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { //创建一个新的链表，比较两个链表将小的值加入这个链表； //创建一个新的链表，比较两个链表将小的值加入这个链表； // 类似于归并排序的合并过程 ListNode dummy = new ListNode(); ListNode cur = dummy; while (list1 != null && list2 != null) { if (list1.val <= list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } cur.next = (list1 == null) ? list2 : list1; return dummy.next; } }

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { // 创建一个最小堆，存储所有的链表的头结点，每次从链表中取出一个节点，并将这个节点的下一个节点放入最小堆中 // 这样就可以保证每次取得当前k个节点的最小值 public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val - b.val); ListNode dummy = new ListNode(-1); ListNode cur = dummy; for (ListNode node :lists) { if (node != null) { // 需要判断是否为空，否则会出现空指针异常，优先队列不能加入空值 pq.offer(node); } } while (!pq.isEmpty()) { cur.next = pq.poll(); cur = cur.next; if (cur.next != null) { pq.offer(cur.next); } } return dummy.next; } }

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { //思路：创建一个链表和原链表相同，再翻转，然后比较；两条链表 if (head == null) { return true; } ListNode headNew = new ListNode(head.val); ListNode curNew = headNew; ListNode cur = head; while (cur.next != null) { // 复制链表 curNew.next = new ListNode(cur.next.val); cur = cur.next; curNew = curNew.next; } ListNode pre = null; curNew = headNew; while (curNew != null) { // 翻转链表 ListNode tmp = curNew.next; curNew.next = pre; pre = curNew; curNew = tmp; } curNew = pre; cur = head; while (curNew != null) { if (curNew.val != cur.val) { return false; } else { curNew = curNew.next; cur = cur.next; } } return true; } }

LeetCode_Hot100_Java_Solution 本文将Leetcode hot 100题目按照类型分类。部分题目可能属于多个类型。 刷leetcode hot 100以前需要了解一些基础知识： 常见排序：冒泡排序，插入排序，选择排序，归并排序，快速排序，堆排序。 时间复杂度为O(nlogn)：归并排序和堆排序。快速排序时间复杂度最好的情况下是O(nlogn)，最坏的情况下是O(n^2)。 字符串的常用方法：length()，substring()，spilt()。 StringBuffer()的常用方法：deleteCharAt()，reverse()，toString()，append()，insert。 常用数据结构及其常用方法：List，HashMap，HashSet，PriorityQueue，stack，queue。 Arrays.sort()自定义排序，PriorityQueue()自定义排序。 数据结构 常用方法 List add()，remove(), get() HashMap put()，size()，remove()，containsKey() HashSet add()，remove()，size()，contains() PriorityQueue poll()，offer()，isEmpty()，size()，peek() stack push()，size()，pop()，isEmpty()，peek() queue poll()，offer()，isEmpty()，size()，peek() dp dp数组和下标的含义，递推公式，初始化，遍历顺序。 ...