链表
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;
}
public void addTail(ListNode head, int data) {
if (head == null) {
return;
}
ListNode newNode = new ListNode(data);
while (head.next != null) {
head = head.next;
}
head.next = newNode;
}
public void forEach(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
}
链表反转
LeetCode206：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
/**
* 递归.
* <p>
* 1. 结束条件 head.next == null;
* 2. 递推公式 head.next.next = head; head.next = null;
* <p>
* 时间复杂度：O(n)
* 空间复杂度：O(n), 其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
*
* @param head
* @return
*/
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
/**
* 迭代.
* <p>
* 时间复杂度：0(n),其中 n 是链表的长度。需要遍历链表一次。
* 空间复杂度：O(1)。
*
* @param head
* @return
*/
public ListNode reverse02(ListNode head) {
ListNode pre = null;
ListNode current = head;
while (current != null) {
ListNode newNode = current.next;
current.next = pre;
pre = current;
current = newNode;
}
return pre;
}
环路检测
LeetCode 面试题 02.08. 环路检测：给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。
/**
* 方法一；哈希表
* 思路与算法：一个非常直观的思路是：我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，
* 就可以判定链表中存在环。借助哈希表可以很方便地实现。
* <p>
* 时间复杂度：O(N),其中 N 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。
* 空间复杂度：O(N),其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。
*
* @param head
* @return
*/
public ListNode detectCycle(ListNode head) {
ListNode pos = head;
Set<ListNode> set = new HashSet<>();
while (pos != null) {
if (set.contains(pos)) {
return pos;
}
set.add(pos);
pos = pos.next;
}
return null;
}
两个有序的链表合并
LeetCode 21. 合并两个有序链表：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/**
* 递归.
* 1. 终止条件 l1 == null || l2 == null
* 2. l1.next = mergeTwoLists
* <p>
* 时间复杂度：O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉l1或者l2的头结点(直到至少有一个链表为空)，
* 函数(mergeTwoList)至多只会递归调用每个节点一次。因此时间复杂度取决于合并后的链表长度，即O(n+m)
* 空间复杂度：O(n+m),其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于
* 递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为O(n+m)
*
* @param l1
* @param l2
* @return
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.data <= l2.data) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
删除链表倒数第n个结点
LeetCode 19. 删除链表的倒数第 N 个结点：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
/**
* 方法一：计算链表长度
* <p>
* 1. 获取链表长度
* 2. 遍历链表，找到节点length-n. 该节点 current.next = current.next.next
* <p>
* 时间复杂度：O(L),其中L为链表长度
* 空间复杂度：O(1)
*
* @param head
* @param n
* @return
*/
public static ListNode removeNthFromEnd01(ListNode head, int n) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode current = pre;
int length = getListNodeLength(head);
int subLength = length - n;
while (subLength != 0) {
current = current.next;
--subLength;
}
current.next = current.next.next;
return pre.next;
}
public static int getListNodeLength(ListNode head) {
int length = 0;
while (head != null) {
++length;
head = head.next;
}
return length;
}
/**
* 方法二：栈
* 先入栈，再出栈
* <p>
* 时间复杂度：O(L)，L链表的长度
* 空间复杂度：O(1)
*
* @param head
* @param n
* @return
*/
public static ListNode removeNthFromEnd02(ListNode head, int n) {
ListNode pre = new ListNode(0, head);
ListNode current = pre;
Deque<ListNode> stack = new LinkedList<>();
while (current != null) {
stack.push(current);
current = current.next;
}
while (n != 0) {
stack.pop();
--n;
}
stack.peek().next = stack.peek().next.next;
return pre.next;
}
/**
* 方法三：双指针.
*
* 时间复杂度：O(L),其中L是链表的长度
* 空间复杂度：O(1)
*
* @param head
* @param n
* @return
*/
public static ListNode removeNthFromEnd03(ListNode head, int n) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode start = pre;
ListNode end = pre;
while (n != 0) {
start = start.next;
n--;
}
while (start.next != null) {
start = start.next;
end = end.next;
}
end.next = end.next.next;
return pre.next;
}
求链表的中间结点
LeetCode 876. 链表中间节点：给定一个头结点为 head 的非空单链表，返回链表的中间结点。
/**
* 1. 求数组长度
* 2. 取值 length/2
* <p>
* 时间复杂度：O(L), 其中L为链表长度。
* 空间复杂度：O(1)
*
* @param head
* @return
*/
public ListNode middleNode(ListNode head) {
int length = 0;
ListNode current = head;
while (current != null) {
++length;
current = current.next;
}
current = head;
for (int i = 0; i < length / 2; i++) {
current = current.next;
}
return current;
}
/**
* 快慢指针.
* 时间复杂度：O(N)O(N)，其中 NN 是给定链表的结点数目
* 空间复杂度：O(1)O(1)，只需要常数空间存放 slow 和 fast 两个指针
*
* @param head
* @return
*/
public ListNode middleNode02(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
