两数相加#2（中等）
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//模拟,时间复杂度O(n),空间复杂度O(n)ListNode ans = new ListNode();ListNode pointer = ans;ListNode p1 = l1, p2 = l2;int carry = 0;while (p1 != null || p2 != null) {int value1 = 0, value2 = 0;if (p1 != null) {value1 = p1.val;p1 = p1.next;}if (p2 != null) {value2 = p2.val;p2 = p2.next;}int temp = value1 + value2 + carry;int curValue = temp >= 10 ? temp - 10 : temp;carry = temp >= 10 ? 1 : 0;pointer.next = new ListNode(curValue);pointer = pointer.next;}//加入最后一个if (carry == 1) pointer.next = new ListNode(carry);return ans.next;}}
删除链表的倒数第N个结点#19（中等）
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//法一:计算长度.时间复杂度O(n),空间复杂度O(1)ListNode dummyNode = new ListNode(0, head);int length = getLenth(dummyNode);ListNode cur = dummyNode;for (int i = 0; i < length - n - 1; i++) {cur = cur.next;}cur.next = cur.next.next;return dummyNode.next;}private int getLenth(ListNode head) {int count = 0;while (head != null) {count++;head = head.next;}return count;}}//==============================================================class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//法二:栈.时间复杂度O(n),空间复杂度O(n)ListNode dummyNode = new ListNode(0, head);Deque<ListNode> stack = new LinkedList<>();ListNode cur = dummyNode;while (cur != null) {stack.push(cur);cur = cur.next;}for (int i = 0; i < n; i++) {stack.pop();}ListNode prev = stack.peek();prev.next = prev.next.next;return dummyNode.next;}}//============================================================class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//法三:双指针.时间复杂度O(n),空间复杂度O(1)ListNode dummyNode = new ListNode(0, head);//注意这里得从head开始ListNode fast = head;for (int i = 0; i < n; i++) {fast = fast.next;}//注意这里要从slow开始ListNode slow = dummyNode;while (fast != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummyNode.next;}}
合并两个有序链表#21（简单）
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//法一:递归.时间复杂度O(m+n),空间复杂度O(m+n)
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
} else if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}
//==================================================================
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//法二:迭代.时间复杂度O(m+n),空间复杂度O(1)
ListNode p1 = list1, p2 = list2;
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
cur.next = p1;
p1 = p1.next;
cur = cur.next;
} else {
cur.next = p2;
p2 = p2.next;
cur = cur.next;
}
}
if (p1 == null) {
cur.next = p2;
} else {
cur.next = p1;
}
return dummyHead.next;
}
}
合并k个升序链表#23（困难）
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//法一:挨个顺序合并.时间复杂度O(n*k^2),空间复杂度O(1)
ListNode ans = null;
int n = lists.length;
for (int i = 0; i < n; i++) {
ans = merge2Lists(ans, lists[i]);
}
return ans;
}
public ListNode merge2Lists(ListNode list1, ListNode list2) {
ListNode dummyNode = new ListNode(0);
ListNode p1 = list1, p2 = list2, cur = dummyNode;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
cur.next = p1;
p1 = p1.next;
} else {
cur.next = p2;
p2 = p2.next;
}
cur = cur.next;
}
cur.next = p1 != null ? p1 : p2;
return dummyNode.next;
}
}
//===================================================================
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//法二:分治.时间复杂度O(nk * logk),空间复杂度O(logk)
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r) {
if (l == r) {
//注意这边返回的是左边，而不是1
return lists[l];
}
if (l > r) {
return null;
}
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
}
//========================================================
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//法三:优先队列.时间复杂度O(kn * logk),空间复杂度O(k)
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((n1, n2) -> {
return n1.val - n2.val;
});
for (ListNode node: lists) {
if (node != null) {
queue.offer(node);
}
}
ListNode head = new ListNode(0);
ListNode tail = head;
while (!queue.isEmpty()) {
ListNode cur = queue.poll();
tail.next = cur;
tail = tail.next;
if (cur.next != null) {
queue.offer(cur.next);
}
}
return head.next;
}
}
两两交换链表中的节点#24（中等）
class Solution {
public ListNode swapPairs(ListNode head) {
//法一：递归。时间复杂度O(n)，空间复杂度O(n)
if (head == null || head.next == null) {
return head;
}
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}
//============================================================
class Solution {
public ListNode swapPairs(ListNode head) {
//法二：迭代。时间复杂度O(n)，空间复杂度O(1)
ListNode dummyNode = new ListNode(0, head);
ListNode temp = dummyNode;
while (temp.next != null && temp.next.next != null) {
ListNode node1 = temp.next;
ListNode node2 = temp.next.next;
node1.next = node2.next;
node2.next = node1;
temp.next = node2;
//注意最后别忘了改变temp的位置
temp = node1;
}
return dummyNode.next;
}
}
//===========================================================
class Solution {
public ListNode swapPairs(ListNode head) {
//法三：栈。时间复杂度O(n)，空间复杂度O(1)
if (head == null || head.next == null) {
return head;
}
Deque<ListNode> stack = new LinkedList<ListNode>();
ListNode dummyNode = new ListNode(-1);
ListNode cur = head;
ListNode p = dummyNode;
while (cur != null && cur.next != null) {
stack.push(cur);
stack.push(cur.next);
cur = cur.next.next;
p.next = stack.pop();
p = p.next;
p.next = stack.pop();
p = p.next;
}
//这个时候cur为null或者cur.next为null，就还有0个或一个元素未添加
p.next = cur;
return dummyNode.next;
}
}
k个一组翻转链表#25（困难）
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
//法一:分段翻转.时间复杂度O(n),空间复杂度O(1)
ListNode dummyNode = new ListNode(-1, head);
ListNode start = dummyNode, end = dummyNode;
while (true) {
for (int i = 0; i < k && end != null; i++) end = end.next;
if (end == null) break;
//翻转后的尾结点
ListNode startNext = start.next;
//下一阶段的头结点
ListNode endNext = end.next;
//切割
end.next = null;
//拼接翻转后的结点。
start.next = myReverse(start.next);
startNext.next = endNext;
//改变，进行下一次循环
end = startNext;
start = end;
}
return dummyNode.next;
}
public ListNode myReverse(ListNode start) {
ListNode cur = start, pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
//官方题解=============================================================
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
//法一:分段翻转.时间复杂度O(n),空间复杂度O(1)
ListNode hair = new ListNode(0);
hair.next = head;
ListNode pre = hair;
while (head != null) {
ListNode tail = pre;
//查看剩余部分长度是否大于等于k
for (int i = 0; i < k; i++) {
tail = tail.next;
if (tail == null) {
return hair.next;
}
}
ListNode nex = tail.next;
ListNode[] reverse = myReverse(head, tail);
head = reverse[0];
tail = reverse[1];
//把子链表接回原链表
pre.next = head;
tail.next = nex;
//改变pre的指向
pre = tail;
head = tail.next;
}
return hair.next;
}
public ListNode[] myReverse(ListNode head, ListNode tail) {
ListNode prev = tail.next;
ListNode p = head;
while (prev != tail) {
ListNode nex = p.next;
p.next = prev;
prev = p;
p = nex;
}
return new ListNode[]{tail, head};
}
}
若有收获，就点个赞吧
0 人点赞
