一文学懂LeetCode链表系列
一文学懂LeetCode链表系列
1. 链表系列解题思路
链表系列的阶梯思路在于指针，这个指针有可能是快慢指针，有可能是指向两个链表的指针。还有一点需要注意的是，借助dumpyNode哑节点保存head信息。
2. 例题详解
2.1 两数相加
给定两个非空链表，表示两个非空整数，按照逆序的方式存储，将这两个数相加，返回一个新的链表。
解题思路
两个链表的相加，肯定是使用指向两个链表的指针，逐位相加，注意处理进位和边界情况。
题解
/**
* 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) {
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
ListNode dumpyNode = new ListNode(0);
ListNode currentNode = dumpyNode;
int carry = 0;
while (l1 != null || l2 != null) {
int sum = 0;
if(l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if(l2 != null) {
sum += l2.val;
l2 = l2.next;
}
sum += carry;
currentNode.next = new ListNode(sum % 10);
carry = (sum) / 10;
currentNode = currentNode.next;
}
if (carry == 1) {
currentNode.next = new ListNode(1);
}
return dumpyNode.next;
}
}
2.2 删除链表的倒数第N个节点
解题思路
删除链表的第N个节点,关键在于找到倒数第N+1个节点，然后将N+1个节点的next跳过倒数第N个节点，指向倒数第N个节点的next。因为是单个链表，所以想到用快慢指针来找倒数第N+1个节点。
题解
/**
* 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 removeNthFromEnd(ListNode head, int n) {
ListNode dumpyNode = new ListNode(0);
dumpyNode.next = head;
ListNode fastNode = head;
ListNode slowNode = dumpyNode;
for(int i = 0; i < n; i++) {
fastNode = fastNode.next;
}
while(fastNode!= null) {
slowNode = slowNode.next;
fastNode = fastNode.next;
}
slowNode.next = slowNode.next.next;
return dumpyNode.next;
}
}
2.3 合并两个有序链表
解题思路
链表的解题在于指针的使用，两个有序链表的话自然想到使用两个指针，逐个元素判断。
题解
/**
* 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 l1, ListNode l2) {
ListNode dumpyNode = new ListNode(0);
ListNode currentNode = dumpyNode;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
currentNode.next = l1;
l1 = l1.next;
} else {
currentNode.next = l2;
l2 = l2.next;
}
currentNode = currentNode.next;
}
if(l1 != null) {
currentNode.next = l1;
}
if(l2 != null) {
currentNode.next = l2;
}
return dumpyNode.next;
}
}
2.4 合并K个有序链表
解题思路
- 合并K个有序链表，可以用循环的方式，依次合并k个链表。
- 也可以使用分治的思想，将k个链表拆成两部分，依次合并。
题解1
/**
* 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 mergeKLists(ListNode[] lists) {
if(lists.length == 0) {
return null;
}
if(lists.length == 1) {
return lists[0];
}
ListNode result = lists[0];
for(int i = 1; i < lists.length; i++) {
result = mergeTwoList(result, lists[i]);
}
return result;
}
private ListNode mergeTwoList(ListNode l1, ListNode l2) {
ListNode dumpyNode = new ListNode(0);
ListNode currentNode = dumpyNode;
while (l1 != null && l2 != null) {
if(l1.val < l2.val) {
currentNode.next = l1;
l1 = l1.next;
} else {
currentNode.next = l2;
l2 = l2.next;
}
currentNode = currentNode.next;
}
if (l1 != null) {
currentNode.next = l1;
}
if (l2 != null) {
currentNode.next = l2;
}
return dumpyNode.next;
}
}
题解2
/**
* 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 mergeKLists(ListNode[] lists) {
return mergeTwoPartsList(lists, 0, lists.length - 1);
}
private ListNode mergeTwoPartsList(ListNode[] lists, int l, int r) {
if (l == r) {
return lists[l];
}
if (l > r) {
return null;
}
int mid = (l + r) / 2;
return mergeTwoList(mergeTwoPartsList(lists, l, mid),
mergeTwoPartsList(lists,mid + 1, r));
}
private ListNode mergeTwoList(ListNode l1, ListNode l2) {
ListNode dumpyNode = new ListNode(0);
ListNode currentNode = dumpyNode;
while (l1 != null && l2 != null) {
if(l1.val < l2.val) {
currentNode.next = l1;
l1 = l1.next;
} else {
currentNode.next = l2;
l2 = l2.next;
}
currentNode = currentNode.next;
}
if (l1 != null) {
currentNode.next = l1;
}
if (l2 != null) {
currentNode.next = l2;
}
return dumpyNode.next;
}
}
2.5 环形链表
判断链表中是否存在环。
解题思路
一个链表的情况，肯定使用的是快慢指针，快指针一次走两步，慢指针一次走一步，如果链表中存在环的话，慢指针一定能追上快指针（其实是快指针追上了慢指针）。
题解
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slowNode = head;
ListNode fastNode = head;
while(fastNode != null &&
fastNode.next != null && fastNode.next.next != null) {
fastNode = fastNode.next.next;
slowNode = slowNode.next;
if (slowNode == fastNode) {
return true;
}
}
return false;
}
}
2.6 环形链表 II
找到环形链表的进入环的节点。
解题思路
设环形链表，环之前的长度为a，环的长度为b。有两个快慢指针fast,slow。fast每次走两步，slow每次走一步。则fast和slow相遇的时候, f 为fast指针走过的路程，s为slow指针走过的路程。
- f = 2s
- f = s + nb
由上可得s=nb。slow指针走到环入口的时候，走的距离就为k=a+nb。那么环入口的位置就是fast和slow相遇之后，有一个节点newNode从head节点开始走，slow和newNode相遇的位置。
题解
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) {
return null;
}
ListNode fastNode = head;
ListNode slowNode = head;
while(fastNode != null && fastNode.next != null) {
slowNode = slowNode.next;
fastNode = fastNode.next.next;
if(slowNode == fastNode) {
fastNode = head;
while (slowNode != fastNode) {
fastNode = fastNode.next;
slowNode = slowNode.next;
}
return slowNode;
}
}
return null;
}
}
2.7 排序链表
解题思路
对链表进行排序，要求时间复杂度为nlog(n), 能想到的就是归并排序。
- 将链表从中间分开
- 对左半部分排序
- 对右半部分排序
- 合并左部分和右部分
题解
/**
* 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 slowNode = head;
ListNode fastNode = head;
ListNode preNode = null;
while(fastNode != null && fastNode.next!= null) {
preNode = slowNode;
slowNode = slowNode.next;
fastNode = fastNode.next.next;
}
preNode.next = null;
ListNode leftPart = sortList(head);
ListNode rightPart = sortList(slowNode);
return mergeList(leftPart, rightPart);
}
private ListNode mergeList(ListNode l1, ListNode l2) {
ListNode dumpyNode = new ListNode(0);
ListNode currentNode = dumpyNode;
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
while (l1 != null && l2 != null) {
if(l1.val < l2.val) {
currentNode.next = l1;
l1 = l1.next;
} else {
currentNode.next = l2;
l2 = l2.next;
}
currentNode = currentNode.next;
}
if (l1 != null) {
currentNode.next = l1;
}
if (l2 != null) {
currentNode.next = l2;
}
return dumpyNode.next;
}
}
2.8 相交链表
求两个相交链表的相交节点。
解题思路
两个链表的问题，肯定是使用两个指针。用指针A指向链表A，指针B指向链表B。相交节点之后的两个链表的长度应该是一致的。如何保证指针A和指针B在走过相同的路程，那就是在指针A到达末尾之后让其指向链表B，指针B达到末尾之后让其指向A，则指针A和B走过相同的路程，就会在交点相遇。
题解
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) {
return null;
}
ListNode p = headA;
ListNode q = headB;
while(p != q) {
if(p == null) {
p = headB;
} else {
p = p.next;
}
if(q == null) {
q = headA;
} else {
q = q.next;
}
}
return p;
}
}
2.9 反转链表
解题思路
就地反转链表的就是将当前节点的的next指针指向前一个节点。在遍历链表的过程中注意保存preNode和nextNode。
题解
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode preNode = null;
while(head != null) {
ListNode nextNode = head.next;
head.next = preNode;
preNode = head;
head = nextNode;
}
return preNode;
}
}
2.10 回文链表
解题思路
判断链表是否为回文链表关键在于回文链表的后半部分和前半部分的倒置链表是否一致。
- 找到中间节点。
- 将后半部分倒置。
- 逐个比较前半部分和倒置后的后半部分。
- 注意处理链表长度为偶数的情况。
题解
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slowNode = head;
ListNode fastNode = head;
while(fastNode != null && fastNode.next != null) {
fastNode = fastNode.next.next;
slowNode = slowNode.next;
}
if(fastNode != null) {
slowNode = slowNode.next;
}
ListNode reverseNode = reverseList(slowNode);
slowNode = head;
while(reverseNode != null) {
if(reverseNode.val != slowNode.val) {
return false;
}
slowNode = slowNode.next;
reverseNode = reverseNode.next;
}
return true;
}
private ListNode reverseList(ListNode head) {
ListNode preNode = null;
while(head != null){
ListNode nextNode = head.next;
head.next = preNode;
preNode = head;
head = nextNode;
}
return preNode;
}
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-12-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录