1. 反转链表
描述
方法一：迭代
思路
假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。
在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode nex = cur.next;cur.next = pre;pre = cur;cur = nex;}return pre;}}
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:pre = Nonecur = headwhile cur:nex = cur.nextcur.next = prepre = curcur = nexreturn pre
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let pre = null;
let cur = head
while (cur != null) {
let nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex;
}
return pre;
};
复杂度分析
- 时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。
- 空间复杂度：O(1)。
方法二：递归
思路
递归版本稍微复杂一些，其关键在于反向工作。假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？
假设列表为：
若从节点
到 
已经被反转，而我们正处于
。
我们希望 的下一个节点指向 。
所以，
。
注意：要小心的是 
的下一个必须指向 Ø 。如果你忽略了这一点，你的链表中可能会产生循环。如果使用大小为 2 的链表测试代码，则可能会捕获此错误。
不妨假设链表为1，2，3，4，5。按照递归，当执行reverseList（5）的时候返回了5这个节点，reverseList(4)中的p就是5这个节点，我们看看reverseList（4）接下来执行完之后，5->next = 4, 4->next = null。这时候返回了p这个节点，也就是链表5->4->null，接下来执行reverseList（3），代码解析为4->next = 3,3->next = null，这个时候p就变成了，5->4->3->null, reverseList(2), reverseList(1)依次类推，p就是:5->4->3->2->1->null
代码
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if (head == null || head.next == null) {
return head;
}
let p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
};
复杂度分析
- 时间复杂度：O(n)，假设 n 是列表的长度，那么时间复杂度为 O(n)。
空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。
2. 两两交换链表中的节点
描述
方法一：递归
思路
这个题目要求我们从第一个节点开始两两交换链表中的节点，且要真正的交换节点。
算法：从链表的头节点 head 开始递归。
- 每次递归都负责交换一对节点。由 firstNode 和 secondNode 表示要交换的两个节点。
- 下一次递归则是传递的是下一对需要交换的节点。若链表中还有节点，则继续递归。
- 交换了两个节点以后，返回 secondNode，因为它是交换后的新头。
- 在所有节点交换完成以后，我们返回交换后的头，实际上是原始链表的第二个节点。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode first = head;
ListNode second = head.next;
first.next = swapPairs(second.next);
second.next = first;
return second;
}
}
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
first = head
second = head.next
first.next = self.swapPairs(second.next)
second.next = first
return second
var swapPairs = function(head) {
if (head == null || head.next == null) {
return head;
}
let first = head;
let second = head.next;
first.next = swapPairs(second.next)
second.next = first
return second;
};
复杂度分析
- 时间复杂度：O(N)，其中 N 指的是链表的节点数量。
- 空间复杂度：O(N)，递归过程使用的堆栈空间。
方法二：迭代
思路
我们把链表分为两部分，即奇数节点为一部分，偶数节点为一部分，A 指的是交换节点中的前面的节点，B 指的是要交换节点中的后面的节点。在完成它们的交换，我们还得用 prevNode 记录 A 的前驱节点。
算法：
firstNode（即 A） 和 secondNode（即 B）分别遍历偶数节点和奇数节点，即两步看作一步。
交换两个节点：
firstNode.next = secondNode.next
secondNode.next = firstNode
还需要更新 prevNode.next 指向交换后的头。
prevNode.next = secondNode
代码
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummpy = ListNode(-1)
dummpy.next = head
pre_node = dummpy
while head and head.next:
first = head
second = head.next
pre_node.next = second
first.next = second.next
second.next = first
pre_node = first
head = first.next
return dummpy.next
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
while(head != null && head.next != null) {
ListNode first = head;
ListNode second = head.next;
pre.next = second;
first.next = first.next.next;
second.next = first;
pre = first;
head = first.next;
}
return dummy.next;
}
}
var swapPairs = function(head) {
let dummy = new ListNode(-1);
dummy.next = head;
let pre = dummy;
while (head != null && head.next != null) {
let firstNode = head;
let secondNode = head.next;
pre.next = secondNode;
firstNode.next = secondNode.next;
secondNode.next = firstNode;
pre = firstNode;
head = firstNode.next;
}
return dummy.next;
};
复杂度分析
- 时间复杂度：O(N)，其中 N 指的是链表的节点数量。
-
3. 回文链表
描述
思路
题目中要求O(1)空间复杂度，所以所有保存链表值，然后再取出来比较的方法都不可能，保存链表值的话，本身就是O(n)了，所以换一种思路来看，从本质来讲的话，链表左右是对称的，所以可以找到链表的中间节点，然后找到头指针，再进行反转链表，最后就是个O(n)的遍历比较。需要考虑的是，翻转前一半还是后一半？
算法 初始化dummy节点（哑巴节点），方便后续处理
- 利用快慢指针找到中间节点
- 翻转链表后一半
- 翻转后的一半和之前记录的链表头结点开始比较，如果出现值不一样，就返回False；如果其中之一能遍历到空，说明是回文。
代码
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode q = slow.next;
ListNode pre = null;
while (q != null) {
ListNode nex = q.next;
q.next = pre;
pre = q;
q = nex;
}
while (head != null && pre != null) {
if (head.val != pre.val) {
return false;
}
head = head.next;
pre = pre.next;
}
return true;
}
}
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
dummy = ListNode(-1)
dummy.next = head
slow = dummy
fast = dummy
while fast and fast.next:
slow = slow.next
fast = fast.next.next
q = slow.next
last = None
while q:
nex = q.next
q.next = last
last = q
q = nex
while head and last:
if head.val != last.val:
return False
head = head.next
last = last.next
return True
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
let dummy = new ListNode(-1);
dummy.next = head;
let slow = dummy;
let fast = dummy;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let q = slow.next;
let pre = null;
while (q != null) {
let nex = q.next;
q.next = pre;
pre = q;
q = nex;
}
while (head != null && pre != null) {
if (head.val != pre.val) {
return false;
}
head = head.next;
pre = pre.next;
}
return true;
};
注意
- 这里我们用了哑巴节点，对于总长度为奇数（不包括dummy）的链表，如，dummy-1-2-3-2-1，slow会指向3，fast会指向4.next.next = null，这个时候翻转，即1-2 和 1-2-3作比较。
- 对于总长度为奇数（不包括dummy）的链表，如，dummy-1-2-3-3-2-1，slow会指向3，fast最后会指向3.next.next = 1，这个时候翻转，即1-2-3 和 1-2-3作比较。
以上两种情况，我们都能得到正确解。无需关注链表长度为奇数还是偶数。
4. K个一组翻转链表
描述
思路
我们需要把链表结点按照 k 个一组分组，所以可以使用一个指针 head 依次指向每组的头结点。这个指针每次向前移动 k 步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于 k。若是，我们就翻转这部分链表，否则不需要翻转。
接下来的问题就是如何翻转一个分组内的子链表。翻转一个链表并不难，过程可以参考 206. 反转链表。但是对于一个子链表，除了翻转其本身之外，还需要将子链表的头部与上一个子链表连接，以及子链表的尾部与下一个子链表连接。
因此，在翻转子链表的时候，我们不仅需要子链表头结点head，还需要有head的上一个结点pre，以便翻转完后把子链表再接回pre。
代码class Solution: def reverseKGroup(self, head: ListNode, k: int) -> ListNode: def reverse(head, tail): prev = tail.next p = head while prev != tail: nex = p.next p.next = prev prev = p p = nex return tail, head dummy = ListNode(-1) dummy.next = head pre = dummy while head: tail = pre # 判断长度是否大于k for i in range(k): tail = tail.next if not tail: return dummy.next nex = tail.next # 返回的是翻转组的头和尾 head, tail = reverse(head, tail) # 进行连接 pre.next = head tail.next = nex # 重新赋值，准备下次翻转 pre = tail head = nex return dummy.nextclass Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre = dummy; while (head != null) { ListNode tail = pre; for (int i = 0; i < k; i++) { tail = tail.next; if (tail == null) { return dummy.next; } } # 记录下一次要反转的头 ListNode nex = tail.next; tail.next = null; # 进行连接 pre.next = reverse(head); pre = head; # 第二次连接 head.next = nex; head = nex; } return dummy.next; } public ListNode reverse(ListNode head) { ListNode pre = null; while (head != null) { ListNode nex = head.next; head.next = pre; pre = head; head = nex; } return pre; } }```javascript var reverseKGroup = function(head, k) { let dummy = new ListNode(-1); dummy.next = head; let pre = dummy; while (head != null) {
let tail = pre; for (let i = 0; i < k; i++) { tail = tail.next; if (tail == null) { return dummy.next; } } let nex = tail.next; tail.next = null; pre.next = reverse(head); pre = head; head.next = nex; head = nex;} return dummy.next; };
var reverse = function(head){ let pre = null; while (head != null) { let nex = head.next; head.next = pre; pre = head; head = nex; } return pre; }
**复杂度分析**
- 时间复杂度：O(n)，其中 n 为链表的长度。head 指针会在 个结点上停留，每次停留需要进行一次 O(k) 的翻转操作。
- 空间复杂度：O(1)，我们只需要建立常数个变量。
**方法二：递归**<br />**思路**<br />递归解题要点：
- 递归的终止条件
- 最终我们要返回什么
- 递归的每一层我们要做什么。
我们先返回头结点，在递归的返回下一组的头结点，记录每一次的尾节点，指向下一次返回的头节点。<br />大致过程可以分解为<br />1、找到待翻转的k个节点（注意：若剩余数量小于 k 的话，则不需要反转，因此直接返回待翻转部分的头结点即可）。<br />2、对其进行翻转。并返回翻转后的头结点（**注意：翻转为左闭又开区间，所以本轮操作的尾结点其实就是下一轮操作的头结点**）。<br />3、对下一轮 k 个节点也进行翻转操作。<br />4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点，即将每一轮翻转的k的节点连接起来。<br />**代码**
```javascript
var reverseKGroup = function(head, k) {
if (head == null) {
return null;
}
let a = head;
let b = head;
for (let i = 0; i < k; i++) {
if (b == null) {
return head;
}
b = b.next;
}
let newHead = reverse(a, b);
a.next = reverseKGroup(b, k)
return newHead;
};
var reverse = function(a, b){
let pre = null;
let cur = a;
let nex;
// 这里 判断 nex != b 也可以，因为while 循环最后一句，是cur = nex
while (cur != b) {
nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex
}
return pre;
}
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
def reverse(a, b):
pre = None
cur = a
while cur != b:
nex = cur.next
cur.next = pre
pre = cur
cur = nex
return pre
a = head
b = head
for i in range(k):
if not b:
return a
b = b.next
# 注意这里遍历完后，b节点指向的是下一组节点的头节点
# 获取翻转后的头结点
new_head = reverse(a, b)
a.next = self.reverseKGroup(b, k)
return new_head
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode a = head;
ListNode b = head;
for (int i = 0; i < k; i++) {
if (b == null){
return a;
}
b = b.next;
}
ListNode newHead = reverse(a, b);
a.next = reverseKGroup(b, k);
return newHead;
}
public ListNode reverse(ListNode a, ListNode b) {
ListNode pre = null;
ListNode cur = a;
while (cur != b) {
ListNode nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex;
}
return pre;
}
}
注意：这里翻转a到b之间的链表，是左闭右开，如 k = 3， 反转 1 - 2 - 3 - 4，此时a 指向 1， b指向 4，反转后为 3 - 2 - 1 - 4，所以有 a.next = reverseKGroup(b, k)，需要注意用cur 来保存a，这样a 最后就变成链表尾部了。
复杂度分析
- 时间复杂度：O(N)
空间复杂度：O（1）我们使用了常数个遍历，并进行递归，递归深度约为（n/k）。
5. 合并K个排序链表
描述
思路
递归归并排序即可，需要注意两个排序链表的合并。
代码var mergeKLists = function(lists) { if (lists.length === 0) { return null; } if (lists.length === 1) { return lists[0]; } if (lists.legnth === 2) { return mergeTwoLists(lists[0], lists[1]); } let mid = lists.length >> 1; let left = lists.slice(0, mid); let right = lists.slice(mid, lists.length); return mergeTwoLists(mergeKLists(left), mergeKLists(right)); }; var mergeTwoLists = function(l1, l2) { const dummy = new ListNode(-1); let p = dummy; while(l1 != null && l2 != null) { if (l1.val < l2.val) { p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; } p = p.next; } p.next = l1 === null? l2 : l1; return dummy.next; };class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: def merge_list(head_a, head_b): pa = head_a pb = head_b pre = ListNode(-1) new_head = pre while pa and pb: if pa.val > pb.val: pre.next = pb pb = pb.next else: pre.next = pa pa = pa.next pre = pre.next if pa: pre.next = pa if pb: pre.next = pb return new_head.next if len(lists) == 0: return None if len(lists) == 1: return lists[0] if len(lists) == 2: return merge_list(lists[0], lists[1]) mid = len(lists) // 2 left_part = self.mergeKLists(lists[:mid]) right_part = self.mergeKLists(lists[mid:]) return merge_list(left_part, right_part)Java迭代版
class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) { return null; } int k = lists.length; int interval = 1; while (interval < k) { for (int i = 0; i < k-interval; i += 2*interval) { lists[i] = merge2Lists(lists[i], lists[i+interval]); } interval *=2; } return lists[0]; } private ListNode merge2Lists(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); ListNode tail = dummyHead; while (l1 != null && l2 != null) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } tail.next = l1 == null? l2: l1; return dummyHead.next; } }注意：这里的终止条件：interval < k = lists.length
6. 两数相加
描述
思路
- 初始化dummy节点
- 遍历两个链表，分别计算ans，carry，cur，pre指向ListNode(cur)，pre= pre.next，p，q指向下一个。
- 注意判断p，q是否为空
- 终止条件为 while p or q
- 结束时，如果carry大于0，需要接在pre后面。
代码
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(-1)
pre = dummy
p = l1
q = l2
carry = 0
while p or q:
a = p.val if p else 0
b = q.val if q else 0
ans = a + b + carry
carry = ans // 10
cur = ans % 10
pre.next = ListNode(cur)
pre = pre.next
if p:
p = p.next
if q:
q = q.next
if carry > 0:
pre.next = ListNode(carry)
return dummy.next
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int a = l1 == null? 0 : l1.val;
int b = l2 == null? 0 : l2.val;
int ans = a + b + carry;
carry = ans / 10;
pre.next = new ListNode(ans % 10);
pre = pre.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry > 0) {
pre.next = new ListNode(carry);
}
return dummy.next;
}
}
var addTwoNumbers = function(l1, l2) {
let dummy = new ListNode(-1);
let pre = dummy;
let carry = 0;
while (l1 != null || l2 != null) {
let a = l1 === null ? 0 : l1.val;
let b = l2 === null ? 0 : l2.val;
let ans = a + b + carry;
carry = Math.floor(ans / 10);
let cur = ans % 10;
pre.next = new ListNode(cur);
pre = pre.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry != 0) {
pre.next = new ListNode(carry);
}
return dummy.next;
};
思考一下如果个位在链表尾部，怎么处理？答案是可以翻转链表，或者将链表放入栈中。对pre指针指向处理不太一样哦！
7. 两数相加 II
描述
思路
我们将链表节点一次放入栈中，那么最后最先弹出的就是个位，这样我们就能进行正常计算了。
代码
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> sta1 = new ArrayDeque<>();
Deque<Integer> sta2 = new ArrayDeque<>();
while (l1 != null) {
sta1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
sta2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode dummy = null;
while (!sta1.isEmpty() || !sta2.isEmpty()) {
int a = sta1.isEmpty() ? 0 : sta1.pop();
int b = sta2.isEmpty() ? 0 : sta2.pop();
int ans = a + b + carry;
carry = ans / 10;
ListNode cur = new ListNode(ans % 10);
cur.next = dummy;
dummy = cur;
}
// 最后carry可能不为0
if (carry != 0) {
ListNode cur = new ListNode(carry);
cur.next = dummy;
dummy = cur;
}
return dummy;
}
}
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
s1,s2 = [], []
while l1:
s1.append(l1.val)
l1 = l1.next
while l2:
s2.append(l2.val)
l2 = l2.next
carry = 0
ans = None
while s1 or s2 or carry != 0:
a = 0 if not s1 else s1.pop()
b = 0 if not s2 else s2.pop()
cur = a + b + carry
carry = cur // 10
cur = cur % 10
curnode = ListNode(cur)
curnode.next = ans
ans = curnode
return ans
8. 环形链表
描述
方法 1：哈希表
思路
如果我们用一个 Set 保存已经访问过的节点，我们可以遍历整个列表并返回第一个出现重复的节点。
代码
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> s = new HashSet<>();
while (head != null) {
if (!s.add(head)) {
return head;
}
head = head.next;
}
return null;
}
}
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
s = set()
while head:
if head not in s:
s.add(head)
head = head.next
else:
return head
return None
方法2：快慢指针
思路
当然一个跑得快的人和一个跑得慢的人在一个圆形的赛道上赛跑，会发生什么？在某一个时刻，跑得快的人一定会从后面赶上跑得慢的人。
初始化两个指针指向头结点，快指针每步走2步，慢指针走一步，如果有环，最终肯定会相遇。
假设相遇点为node h，则有 2 （F + a）= F + a + b + a ， 可得 F = b。
所以我们找到相遇点， 然后从相遇点和头结点一起出发，就会到达环的入口节点。
*代码
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
ListNode meet = null;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
meet = slow;
break;
}
}
if (meet == null) {
return null;
}
ListNode p1 = head;
while (p1 != meet) {
p1 = p1.next;
meet = meet.next;
}
return p1;
}
}
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = head
fast = head
meet = None
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
meet = slow
break
if not meet:
return None
while head != meet:
head = head.next
meet = meet.next
return head
var detectCycle = function(head) {
let slow = head;
let fast = head;
let meet = null;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
meet = slow;
break;
}
}
if (meet === null) {
return null;
}
while (head != meet) {
head = head.next;
meet = meet.next;
}
return head;
};
注意: 找到meet之后应该break，否则会死循环。
9. 相交链表
描述
方法一：快慢指针
思路
如果两个链表相交，那么相交点之后的长度是相同的
我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。
为此，我们必须消除两个链表的长度差
指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时，长度差就消除了
如此，只需要将最短链表遍历两次即可找到位置
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pa = headA;
ListNode pb = headB;
while (pa != pb) {
pa = pa == null ? headB: pa.next;
pb = pb == null ? headA: pb.next;
}
return pa;
}
}
方法二：求长度
思路
我们可以求出两个链表的长度，然后，指定两个指针，让指向长链表的指针先移动长度差的距离，这样剩下要走的距离就一致了。
代码
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
def getLength(node):
count = 0
while node:
node = node.next
count +=1
return count
p = headA
q = headB
lenA = getLength(headA)
lenB = getLength(headB)
if lenA > lenB:
for i in range(lenA-lenB):
p = p.next
else:
for i in range(lenB-lenA):
q = q.next
while p and q:
if p == q:
return q
p = p.next
q = q.next
return None
10. 排序链表
描述
思路
题目要求O(n log n)的时间复杂度，很明显需要用归并排序或者快速排序，这里肯定使用归并排序。
归并排序，每次需要求中点位置，我们用快慢指针，快指针每次走两步，当快指针指向最后一个节点时，慢指针就刚好指向中间位置。
然后我们对两个链表进行归并。
我们需要记录，头结点，求中间节点，还需要一个dummy节点来作为最终链表的头结点的上一个元素。
代码
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// mid 表示右半段链表的头结点
ListNode mid = slow.next;
// 前半段链表的尾结点指向空
slow.next = null;
// 递归求解
ListNode left = sortList(head);
ListNode right = sortList(mid);
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
while (left != null && right != null) {
if (left.val < right.val) {
p.next = left;
left = left.next;
} else {
p.next = right;
right = right.next;
}
p = p.next;
}
// 当其中一个链表遍历完了，就指向另一个链表
p.next = left == null ? right : left;
return dummy.next;
}
}
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
left = self.sortList(head)
right = self.sortList(mid)
new_head = ListNode(0)
p = new_head
while left and right:
if left.val < right.val:
p.next = left
left = left.next
else:
p.next = right
right = right.next
p = p.next
p.next = left if left else right
return new_head.next
var sortList = function(head) {
if (head == null || head.next == null) {
return head;
}
let slow = head;
let fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
let mid = slow.next;
slow.next = null;
let leftHead = sortList(head);
let rightHead = sortList(mid);
let dummy = new ListNode(-1);
let p = dummy;
while (leftHead !== null && rightHead !==null) {
if (leftHead.val < rightHead.val) {
p.next = leftHead;
leftHead = leftHead.next;
} else {
p.next = rightHead;
rightHead = rightHead.next;
}
p = p.next;
}
p.next = leftHead == null ? rightHead : leftHead;
return dummy.next;
};
11. 移除重复节点
描述
思路
显然我们可以两重循环，暴力求解。题目要求去除重复节点，我们可以使用set来保存节点的值，进行去重。
我们需要两个指针，一个遍历，一个来保存要删除节点的前一个节点。
原理
- 初始化集合s，p指向head, q指向head.next，将q加入s中
- 用指针q进行遍历
- 如果q不在s中出现，就把q放入s，同时右移动一位p, q
- 如果q 在s中出现过，说明要删除q，执行q = q.next p.next = q
- 最后返回head
代码
class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
if (head == null || head.next == null) {
return head;
}
Set<Integer> s = new HashSet<>();
ListNode p = head;
ListNode q = head.next;
s.add(p.val);
while (q != null) {
if (!s.add(q.val)) {
q = q.next;
p.next = q;
} else {
p = p.next;
q = q.next;
}
}
return head;
}
}
class Solution:
def removeDuplicateNodes(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
s = set()
p = head
s.add(p.val)
q = p.next
while q:
if q.val not in s:
s.add(q.val)
q = q.next
p = p.next
else:
q = q.next
p.next = q
return head
12. 删除排序链表中的重复元素
描述
思路
这道题要我们删除所有的重复节点，链表是排序的，所以我们需要记录每个节点的前驱，然后判断该节点和后续节点是否是重复元素，来决定是否进行删除。
很明显我们需要一个dummy节点，因为第一个节点可能就是重复节点，我们需要一个pre保存前驱，一个nex作为当前节点的下一个节点。如果连续相等，我们就nex = nex.next，我们还需要一个遍历指针。
原理
1.需要一个哨兵节点，指向整个链表的head，用于最后返回结果链表。
2.遍历过程中，首先需要一个遍历指针（快指针），遇到相同的节点，需要有跳过相同值节点的操作，
快指针在最基本的只有两个节点值相同的情况下，至少指向第一个相同的节点，此时需要有前继节点（慢指针）
的记录，将前继节点指向最后一个相同节点的下一位。
3.明确了需要记录和操作的节点后，进行正常的遍历逻辑即可。
代码
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
// pre记录前驱
ListNode pre = dummy;
while (head != null) {
// nex记录后驱
ListNode nex = head.next;
if (nex != null && nex.val == head.val) {
// 如果一直相等就右移nex
while (nex !=null && nex.val == head.val) {
nex = nex.next;
}
// 更新pre 和 head
pre.next = nex;
head = nex;
} else {
// 如果不相等，两个一起右移
pre = head;
head = head.next;
}
}
return dummy.next;
}
}
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
pre = dummy
while head:
nex = head.next
if nex and head.val == nex.val:
while nex and head.val == nex.val:
nex = nex.next
pre.next = nex
head = nex
else:
pre = head
head = head.next
return dummy.next
13. 复杂链表的复制
思路
hash表保存节点和值生成的新节点的映射关系，两次遍历就ok。哈希表存的是 node 和 Node(node.val)
代码
Python代码：
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
p = head
dic = {None: None}
while p:
dic[p] = Node(p.val)
p = p.next
p = head
while p:
dic[p].next = dic[p.next]
dic[p].random = dic[p.random]
p = p.next
return dic[head]
Java代码：
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
HashMap<Node, Node> map = new HashMap<>();
Node p = head;
while(p != null) {
map.put(p, new Node(p.val));
p = p.next;
}
p = head;
while(p != null) {
map.get(p).next = map.get(p.next);
map.get(p).random = map.get(p.random);
p = p.next;
}
return map.get(head);
}
}
14. 逆置链表位置m到n的节点
描述
将链表第m到第n个位置的节点进行翻转。
思路
我们肯定要保存第m个位置节点的前驱节点，我们还保存一下翻转之前，m位置的节点，因为翻转之后，它就跑到链表尾部了。然后我们进行翻转，翻转的长度为 n - m + 1，刚好nex保存n位置之后的节点，翻转后我们进行连接操作。需要判断 pre 是否为None，如果翻转位置是1开始，我们直接返回翻转后的头结点即可。
代码
Python代码：
def reverse_between(self, m, n, head):
change_len = n-m+1
res = head
pre_head = None
while head and m-1 > 0:
pre_head = head
head = head.next
m = m - 1
modify_list_tail = head
modify_list_head = None
while head and change_len > 0:
next = head.next
head.next = modify_list_head
modify_list_head = head
head = next
change_len -= 1
modify_list_tail.next = next
if pre_head:
pre_head.next = modify_list_head
else:
res = modify_list_head
return res
若有收获，就点个赞吧
0 人点赞
