leetcode链表总结
链表
总结：链表的题目一定要把链表画出来，多去画一画，想一想，不会很难，但是要十分注意细节，很容易出错。
- 链表不像数组，数组会结合很多技巧和算法，链表的题只需要常规的去一步一步的思考，考虑清楚边界，头结点和尾结点的处理，考虑清楚下一个节点到底是哪一个，一步一步的即可。
- 链表中考虑清楚边界，需要考虑清楚头结点和尾结点如何处理，常常新建一个节点，该节点指向头结点，这样保持对头结点的访问和处理，把头结点当做一个普通节点考虑到处理过程中。
- 单链表的从左到右顺序访问可以和树的中序遍历结合，而有序的单链表可以和二叉平衡搜索树结合。
- 链表常常结合双指针，尤其通过快慢指针找链表的中点。
1. 206 反转单链表I
- 方法一：迭代的方法实现，很简单，只需要O(1)的空间复杂度，O(n)的时间复杂度，中间临时节点保留节点信息，不断将两两节点指向关系反转。
/**
* 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)
return head;
ListNode headResult = new ListNode(head.val);
headResult.next = null;
head = head.next;
while(head != null){
ListNode temp = head.next;
head.next = headResult;
headResult = head;
head = temp;
}
return headResult;
}
}
- 方法二：递归的方法实现，反转链表时如果从前往后考虑那就是迭代的方式实现，如果反过来考虑问题，从后往前反转，就是递归实现，利用递归先递归到达链表最末尾节点，然后再从后面开始逐步向前，把两两节点指向关系反转，本来链表具有单向指向关系，无法获得前驱节点，但是通过递归+类似回溯，就从另外的角度得到了前驱节点的信息。空间复杂度O(1)，时间复杂度O(n)。
/**
* 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;
else{
ListNode headResult = reverseList(head.next);
head.next.next = head;
head.next = null;
return headResult;
}
}
}
- 方法三：类似于字符串反转，递归方法，上面两种方法都是直接修改节点的指向关系来实现，还可以不改变链表中节点的指向关系，直接交换各个节点中的数据来实现，就像字符串反转一样，从两端开始两两交换，并不断向中心移动，实现反转，但是字符串反转时可以转化成数组，数组的索引很方便；在单链表中没发像数组那样灵活的索引，但是可以通过递归+类似回溯实现。考虑递归的一个f(x)，返回右移后的left节点，结束条件是递归到右边界，f(x)为的当前两端两个节点值，实现反转，因此递归函数需要一个变量指针指向left一个指向right，每次交换left和right的值，且left右移，right左移。时间复杂度是O(n)，空间复杂度是O(1)。
/**
* 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;
recursion(head, head);
return head;
}
private ListNode recursion(ListNode left, ListNode right){
if(right == null)
return left;
left = recursion(left, right.next);
// 为了使得递归在完成两两交换后即到达中心位置时停下来，链表长度是奇数时在中心相遇，偶数时right在left左边
if(left == right || right.next == left){
left = null;
}
// 加入判断使其在停下来后不再进行交换
if(left != null){
swap(left, right);
left = left.next;
}
return left;
}
// 交换两个节点的值
private void swap(ListNode left, ListNode right){
int temp = left.val;
left.val = right.val;
right.val = temp;
}
}
92 反转单链表II
- 方法一：迭代的方法去反转链表，和反转单链表I的过程类似，只不过这里要求的是反转指定范围内的单链表，需要保持未反转链表与反转链表的顺序，需翻转部分的链表与该部分后面的不需翻转的链表，在反转后的相对顺序是一致的，因为迭代的方法在反转后尾结点会指向下一个待反转节点，但是反转部分之前的节点需要标记，并将其与反转部分的头结点相连接。把链表拆成三部分来看就好理解，1->2->3，假设需要反转的范围是[2,2]，三部分分别是：需翻转链表2；需翻转之前的1；需翻转之后的3。时间复杂度是O(n)，空间复杂度是O(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
int count = 1;
ListNode tempHead = head;
ListNode pre = null;
while(count < m){
pre = tempHead;
tempHead = tempHead.next;
++count;
}
ListNode cur = tempHead;
ListNode next = null;
ListNode tempTail = tempHead;
while(count < n){
next = cur.next;
cur.next = next.next;
next.next = tempHead;
tempHead = next;
++count;
}
if(pre != null)
pre.next = tempHead;
else
head = tempHead;
return head;
}
}
- 方法二：递归，参考反转链表I递归有两种方式，一种是递归到需要反转的子链表的尾结点然后从后往前一个一个的反转节点的指向；另外一种方式是类似于字符串反转，两两交换需要反转的链表的节点值，从两头向中心移动完成链表反转。这里只给出第二种递归的方式。这里递归的方式解决不如迭代，但是当做练习递归吧。考虑递归只需考虑返回值，一个f(x)，以及终止条件，写出框架后，不断修改f(x)，这里复杂就复杂在，递归调用本身会区分不同的条件，left和right同时右移 left不动right右移 这两种，而每一种条件下的调用中f(x)的处理是相同的。由于递归的天然属性就是从后往前，因此right天然会往中心移动，只需考虑left不断向右移动即可。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
private int M = 1, N = 1;
public ListNode reverseBetween(ListNode head, int m, int n) {
recursion(head, head, m, n);
return head;
}
private ListNode recursion(ListNode left, ListNode right, int m, int n){
if(M == m && N == n){
return left;
} else if(M < m && N <n) {
left = left.next;
++M;
right = right.next;
++N;
left = recursion(left, right, m, n);
if(M >= m && N <= n && M < N) {
swap(left, right);
left = left.next;
++M;
--N;
return left;
}
} else if(M == m && N < n) {
right = right.next;
++N;
left = recursion(left, right, m, n);
if(M >= m && N <= n && M < N) {
swap(left, right);
left = left.next;
++M;
--N;
return left;
}
}
return left;
}
private void swap(ListNode left, ListNode right){
int temp = left.val;
left.val = right.val;
right.val = temp;
}
}
2. 141 环形链表I 判断链表是否有环
- 方法一：快慢指针，如果有环，则快指针一定能追上慢指针，也就是不断循环之后，快指针会和慢指针指向同一个节点，空间复杂度是O(1)，时间复杂度是O(n)。
/**
* 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) {
if(head == null || head.next == null)
return false;
ListNode slowHead = head;
ListNode fastHead = head;
while(fastHead != null && fastHead.next != null){
slowHead = slowHead.next;
fastHead = fastHead.next.next;
if(slowHead == fastHead)
return true;
}
return false;
}
}
- 方法二：哈希表法，我们只要遍历一遍链表，记录每一个已经遍历过的节点，当遍历到null时说明没有环，否则一定会遍历到已经遍历过的节点，则是有环，只需要保存遍历过的节点的记录即可，适合记录的就是哈希表，java中用HashMap有些浪费空间，HashSet足够了，时间复杂度是O(n),空间复杂度是O(n)。
/**
* 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) {
HashSet<ListNode> hash = new HashSet<>();
while(head != null){
if(hash.contains(head))
return true;
else{
hash.add(head);
head = head.next;
}
}
return false;
}
}
142 环形链表II
- 方法一：哈希表法，遍历链表，判断节点是否存在于HashSet中，并不断将不在其中的放入HashSet，如果遇到空节点，则没有环返回null，否则一定会遇到当前节点已经存在于HashSet中，则返回当前节点。这是一种暴力方法，时间复杂度是O(n),空间复杂度是O(n)。进阶要求不用额外的空间。
/**
* 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;
HashSet<ListNode> set = new HashSet<>();
while(head != null){
if(set.contains(head))
return head;
set.add(head);
head = head.next;
}
return head;
}
}
- 方法二：进阶要求：不使用额外的地址空间。leetcode官方题解https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode/中“方法 2：Floyd 算法”，通过数学证明了；但是看到了更通俗的解释：
- 看不懂算式证明的话，可以这样解释性地来理解阶段：
- 快指针1次走2步，慢指针1次走1步。所以快指针总是走了慢指针两倍的路。
- 回顾一下阶段1的过程，设头节点到入环点的路途为 n, 那么慢指针走了入环路途的一半（n/2）时，快指针就到达入环点了(走完n了)。
- 慢指针再继续走完剩下的一般入环路途（剩下的n/2），到达入环点时，快指针已经在环内又走了一个 n 那么远的路了。
- 为了方便理解，这里先讨论环很大，大于n的情况（其他情况后文补充）。此时，慢指针正处于入环点，快指针距离入环点的距离为n。环内路，可以用此时快指针的位置分割为两段，前面的 n 部分，和后面的 b 部分。
- 此时开始继续快慢指针跑圈，因为已经在环内了，他们其实就是在一条nbnbnbnbnbnbnb（无尽nb路）上跑步。
- 慢指针从入环处开始跑b步，距离入环处就剩下了n。此时，快指针则是从距离入环处n步远的位置开始跑了2b步，距离入环处也是剩下了n。他们相遇了，并且距离入环处的距离就是n，n就是头节点到入环点的距离阿!!!后面的不用说了吧。环很小的情况，其实跟环很大是一样的，比如你可以理解为将多个小环的循环铺开，虚拟扩展成一个大环来理解。
- 时间复杂度是O(n)，空间复杂度是O(1)。
/**
* 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 fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow)
break;
}
// 为null则说明链表无环
if(fast == null || fast.next == null)
return null;
// 从链表头部及重合点开始找二者重合点，重合点即环的入口
ListNode head1 = head;
ListNode head2 = fast;
while(head1 != head2){
head1 = head1.next;
head2 = head2.next;
}
return head1;
}
}
3. 160 相交链表 判断两个链表的相交与否，如果相交返回其交点节点
- 方法一：双指针的方法：其实可以这么理解，如果第一次前进a走五步，b走三步，那么下一次怎么走a和b能走得总共一样远？答案就是下一次走时候，a走上一次b走的步数三步，b走a上一次走的步数五步；那么两次加起来一共都是走了八步，就总共走得一样远了。这道题也是这个道理，同时遍历这两个链表，当第一个链表当前遍历的节点为null时，令其为headB的头结点，当第二个链表当前遍历的节点为null时，令其为headA的头结点；那么类似地上面的例子，当两者都遍历完自身并遍历完另外一个链表时，二者会走得一样远，此时如果是有交点则二者位于交点上，如果没有交点则二者都是null，空间复杂度是O(1)，时间复杂度是O(m+n)。
/**
* 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 a = headA;
ListNode b = headB;
while(a != b){
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}
- 方法二：哈希表的方法：遍历其中一个链表，保存其所有节点到HashSet中，然后遍历另外一个链表，判断当前节点是否在另外一个链表中，如果从某一个节点开始每一个节点在另外一个链表中都有，则说明相交节点就是这个第一个开始重复的节点，空间复杂度O(m)或者是O(n)取决于遍历哪一个放入HashSet中，时间复杂度是O(m+n)。
/**
* 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;
HashSet<ListNode> hash = new HashSet<>();
ListNode a = headA;
while(a != null){
hash.add(a);
a = a.next;
}
ListNode b = headB;
while(b != null){
if(hash.contains(b)){
return b;
}
b = b.next;
}
return null;
}
}
4. 24 两两交换链表中的节点
- 方法一：递归法：递归时不要考虑整个递归栈的调用，只需要抓住最后一个f(x)的处理过程即可，且抓住最后一个处理过程中的三部分，1、返回值2、当前调用的处理函数内容3、终止条件；这个题是要两两进行交换，抓住一个处理过程就是抓住一次两两交换，对于当前两个节点的交换假设前一个节点是head后一个节点是next，则交换后head在next的后面，则head的下一个节点是后一对交换节点的头节点即下一次调用的返回值，终止条件是没有节点或者只剩下一个节点时，牢记一点，考虑这个问题只需要关注一次两两交换，时间复杂度是O(n)，空间复杂度是O(1)。
/**
* 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 next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
}
- 方法二：迭代法：比较常规，但是比较繁琐，容易出错，就是保持对三个连续节点的可达访问，进行两两交换即可，时间复杂度是O(n)，空间复杂度是O(1)。
/**
* 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 pre = new ListNode(0);
pre.next = head;
ListNode cur = head;
ListNode result = head.next;
while(cur != null && cur.next != null){
pre.next = cur.next;
cur.next = pre.next.next;
pre.next.next = cur;
pre = cur;
cur = cur.next;
}
return result;
}
}
5. 707 设计链表
- 题目比较简单，但是在做的时候很多细节需要注意，不要出错误，下面是自己写的单链表
class MyLinkedList {
private class ListNode {
public int value;
public ListNode next;
public ListNode(){
this.value = 0;
this.next = null;
}
public ListNode(int value){
this.value = value;
this.next = null;
}
}
public ListNode head;
public ListNode tail;
public int size;
/** Initialize your data structure here. */
public MyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if(index >= 0 && index < size){
ListNode temp = this.head;
for(int i = 0; i <= index; i++){
if(i == index)
return temp.value;
temp = temp.next;
}
}
return -1;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
if(size == 0){
ListNode temp = new ListNode(val);
head = temp;
tail = temp;
++size;
}
else{
ListNode temp = new ListNode(val);
temp.next = this.head;
head = temp;
++size;
}
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
if(size == 0){
ListNode temp = new ListNode(val);
tail = temp;
head = temp;
++size;
}else{
ListNode temp = new ListNode(val);
tail.next = temp;
tail = temp;
++size;
}
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
if(index == size)
addAtTail(val);
else if(index > size)
return;
else if(index <= 0)
addAtHead(val);
else{
ListNode cur = this.head;
for(int i = 0; i < index; i++){
if(i == index - 1){
ListNode temp = new ListNode(val);
temp.next = cur.next;
cur.next = temp;
++size;
}else
cur = cur.next;
}
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if(index < 0 || index >= size)
return;
else if(index == 0){
head = head.next;
--size;
}
else if(index == size - 1){
ListNode cur = this.head;
for(int i = 0; i < size - 1; i++){
if(i == size - 2){
cur.next = cur.next.next;
tail = cur;
--size;
}else
cur = cur.next;
}
}
else{
ListNode cur = this.head;
for(int i = 0; i < index; i++){
if(i == index - 1){
cur.next = cur.next.next;
--size;
}else
cur = cur.next;
}
}
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
- 下面是Java源码中LinkedList的源码
6. 328 奇偶链表
- 按照题目要求去思考，第一个节点是1，将索引为奇数的节点按原来的顺序排列在一起，将索引为偶数的节点按原来的顺序排列在一起，所有奇数节点排列在偶数节点之前；就按照这种方式去解决，将奇数索引的节点排列起来，然后将偶数节点排列起来，最后把奇数排列连接在偶数排列的前面
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null || head.next.next == null)
return head;
ListNode oddHead = head;
ListNode oddTail = head;
ListNode evenHead = head.next;
ListNode evenTail = head.next;
while(evenTail != null && evenTail.next != null){
oddTail.next = evenTail.next;
oddTail = oddTail.next;
evenTail.next = oddTail.next;
evenTail = evenTail.next;
}
oddTail.next = evenHead;
return oddHead;
}
}
7. 817 链表组件
- 仔细读题目，一开始看错了题目，以为是输出G中元素在链表中连续出现的最长的子链表；用HashMap去记录数组G中元素，这样在查找链表当前元素在数组G中是否出现时可以通过HashMap去判断，HashMap的查找速度是O(1)，这样整体的时间复杂度就是O(n)，空间复杂度是O(k)k为数组G中的元素个数。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int numComponents(ListNode head, int[] G) {
if(G.length == 1)
return 1;
int result = 0;
int count = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for(int x : G)
map.put(x, 0);
while(head != null){
if(map.containsKey(head.val)){
count++;
head = head.next;
}else{
result = count == 0 ? result : result + 1;
count = 0;
head = head.next;
}
}
result = count == 0 ? result : result + 1;
return result;
}
}
8. 86 分隔链表
- 方法一:这道题和上一道奇偶链表的题目类似，只不过这里不是以奇偶来区分的，而是用小于目标值和大于等于目标值来区分的；同样采用把源链表分割成两个链表，一个是所有节点值都小于目标值，一个是所有节点值都大于等于目标值，然后把小于的链表结尾链接上大于等于的链表的头部。时间复杂度O(n)，空间复杂度是O(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null || head.next == null)
return head;
ListNode smallerHead = null, smallerTail = null, biggerHead = null, biggerTail = null;
while(head != null){
if(head.val < x){
if(smallerHead == null && smallerTail == null){
smallerHead = head;
smallerTail = head;
head = head.next;
smallerTail.next = null;
} else {
smallerTail.next = head;
smallerTail = smallerTail.next;
head = head.next;
smallerTail.next = null;
}
} else {
if(biggerHead == null && biggerTail == null){
biggerHead = head;
biggerTail = head;
head = head.next;
biggerTail.next = null;
} else {
biggerTail.next = head;
biggerTail = biggerTail.next;
head = head.next;
biggerTail.next = null;
}
}
}
if(smallerTail == null)
return biggerHead;
smallerTail.next = biggerHead;
return smallerHead;
}
}
9. 143 重排链表
- 方法一：递归，这个题目和之前做过的206反转单链表(笔记中的第1题)采用的递归思路一致；由于题目要求重排就是从第一个节点开始，重排为一个最左边的节点接一个最右边的节点，先递归至最右边数第二节点，然后开始重排，每次左边数一个，右边数一个进行连接重排，当左右指针碰撞时停止重排。时间复杂度O(n)，空间复杂度是O(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if(head == null || head.next == null || head.next.next == null)
return;
recursion(head, head.next);
}
private ListNode recursion(ListNode head, ListNode tail){
// System.out.println("当前调用栈前head:"+head.val+",tail:"+tail.val);
if(tail.next == null)
return head;
head = recursion(head, tail.next);
if(head != tail && head != null){
tail.next.next = head.next;
head.next = tail.next;
tail.next = null;
head = head.next.next;
}
// if(head == null)
// System.out.println("当前调用栈后head:null"+",tail:"+tail.val);
// else
// System.out.println("当前调用栈后head:"+head.val+",tail:"+tail.val);
if(head == tail)
head = null;
return head;
}
}
- 方法二：看了别人的解答，看到了另外一种解法，分为3步：
- 利用快慢指针找到链表的中间节点，将链表一分为二；
- 将链表的后半部分进行反转；
- 从两个链表的头部开始合并两个链表。
时间复杂度是O(n)，空间复杂度是O(1)，但是这种方法的开销是比递归的方法大的，不过逻辑清晰。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode head1 = head;
ListNode head2 = head;
// 找到链表的一半
while (head2.next != null && head2.next.next != null) {
head1 = head1.next;
head2 = head2.next.next;
}
// 将链表分为两段
head2 = head1.next;
head1.next = null;
head1 = head;
// 将后半段进行链表的翻转
ListNode cur = head2;
ListNode next;
while (cur.next != null) {
next = cur.next;
cur.next = next.next;
next.next = head2;
head2 = next;
}
// 两条链表进行合并
ListNode next1;
ListNode next2;
while (head2 != null) {
next1 = head1.next;
next2 = head2.next;
head1.next = head2;
head2.next = next1;
head1 = next1;
head2 = next2;
}
}
}
10. 82 删除排序链表中的重复元素II
- 通过指针fast去判断重复的值并利用fast指针不断跳过重复节点，但是会剩下重复节点的最后一个，因此在slow指针连接时需要跳过这个重复值。时间复杂度O(n)，空间复杂度O(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode result = new ListNode(0);
result.next = head;
ListNode slow = result;
ListNode fast = result.next;
while(fast != null){
while(fast.next != null && fast.val == fast.next.val)
fast = fast.next;
if(slow.next == fast)
slow = fast;
else
slow.next = fast.next;
fast = fast.next;
}
return result.next;
}
}
11. 2 两数相加I
- 回想数组中的两数相加，按照竖式的格式进行加法计算，保持进位，这个题目中的链表表示的数字本身就是低位在左高位在右的，也就是本身就是逆序的，因此直接从左边开始遍历相加即可。时间复杂度O(m + n)m n 分别是两个加数链表的长度，空间复杂度是O(m + n)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode headResult = result;
int count = 0;
int number = 0;
while(l1 != null && l2 != null){
number = l1.val + l2.val + count;
count = number / 10;
ListNode temp = new ListNode(number % 10);
headResult.next = temp;
headResult = headResult.next;
l1 = l1.next;
l2 = l2.next;
}
while(l1 != null){
number = l1.val + count;
count = number / 10;
ListNode temp = new ListNode(number % 10);
headResult.next = temp;
headResult = headResult.next;
l1 = l1.next;
}
while(l2 != null){
number = l2.val + count;
count = number / 10;
ListNode temp = new ListNode(number % 10);
headResult.next = temp;
headResult = headResult.next;
l2 = l2.next;
}
if(count != 0){
ListNode temp = new ListNode(count);
headResult.next = temp;
headResult = headResult.next;
}
return result.next;
}
}
445 两数相加II
- 方法一：参考数组中的两数相加，由于加法竖式中从右往左加，我们就从右往左遍历，逐位相加，并保持进位值；但是单链表无法从右往左遍历，我们可以先把链表反转，然后从左向右遍历，参考数组中两数相加的方式求解。时间复杂度是O(m + n)m n 分别是两个链表的长度，空间复杂度是O(m + n)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head1 = reverseList(l1);
ListNode head2 = reverseList(l2);
int count = 0;
int number = 0;
ListNode result = new ListNode(0);
ListNode headResult = result;
while(head1 != null && head2 != null){
number = head1.val + head2.val + count;
count = number / 10;
ListNode temp = new ListNode(number % 10);
headResult.next = temp;
headResult = headResult.next;
head1 = head1.next;
head2 = head2.next;
}
while(head1 != null){
number = head1.val + count;
count = number / 10;
ListNode temp = new ListNode(number % 10);
headResult.next = temp;
headResult = headResult.next;
head1 = head1.next;
}
while(head2 != null){
number = head2.val + count;
count = number / 10;
ListNode temp = new ListNode(number % 10);
headResult.next = temp;
headResult = headResult.next;
head2 = head2.next;
}
if(count != 0){
ListNode temp = new ListNode(count);
headResult.next = temp;
headResult = headResult.next;
}
return reverseList(result.next);
}
private ListNode reverseList(ListNode head){
if(head.next == null)
return head;
ListNode cur = head;
ListNode next = head.next;
while(cur.next != null){
next = cur.next;
cur.next = next.next;
next.next = head;
head = next;
}
return head;
}
}
- 方法二：进阶要求，不能反转链表，怎么做？考虑到需要从后往前遍历，而且不能反转，那么只能是通过递归或者用栈的方式进行，此处尝试用栈进行解决，其实也简单，只需要遍历两个链表并放入两个栈中，由于栈的先入后出，从栈中取元素，自然就是从后往前遍历。时间复杂度O(m + n)m n 分别是两个链表的长度，空间复杂度O(m + n)，用栈的操作引入的时空复杂度换取实现进阶要求。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack stack1 = getStack(l1);
Stack stack2 = getStack(l2);
int count = 0;
int number = 0;
Stack<ListNode> stack = new Stack<>();
while(!stack1.empty() && !stack2.empty()){
number = ((ListNode)stack1.pop()).val + ((ListNode)stack2.pop()).val + count;
count = number / 10;
ListNode temp = new ListNode(number % 10);
stack.push(temp);
}
while(!stack1.empty()){
number = ((ListNode)stack1.pop()).val + count;
count = number / 10;
ListNode temp = new ListNode(number % 10);
stack.push(temp);
}
while(!stack2.empty()){
number = ((ListNode)stack2.pop()).val + count;
count = number / 10;
ListNode temp = new ListNode(number % 10);
stack.push(temp);
}
if(count != 0){
ListNode temp = new ListNode(count);
stack.push(temp);
}
ListNode result = stack.pop();
ListNode headResult = result;
while(!stack.empty()){
headResult.next = stack.pop();
headResult = headResult.next;
}
return result;
}
private Stack<ListNode> getStack(ListNode head){
Stack<ListNode> stack = new Stack<>();
while(head != null){
stack.push(head);
head = head.next;
}
return stack;
}
}
12. 19 删除链表的倒数第N个节点
- 方法一：用栈来实现，时间复杂度O(m + n)m n 分别为链表长度和给定的n，空间复杂度为O(m)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null)
return head;
Stack<ListNode> stack = new Stack<>();
ListNode temp = head;
while(temp != null){
stack.push(temp);
temp = temp.next;
}
ListNode cur = null;
while(n >= 1){
cur = stack.pop();
--n;
}
if(cur == head){
head = head.next;
}else{
ListNode pre = stack.pop();
pre.next = cur.next;
}
return head;
}
}
- 方法二：双指针，进阶要求用一趟扫描实现。我们可以使用两个指针。快指针从开头向前移动n+1步，而慢指针将从开头出发。现在，这两个指针之间有n个节点相隔。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到快指针到达null。此时慢指针将指向倒数第n+1个节点。我们重新链接慢指针所引用的结点的 next 指针指向该结点的下下个结点，从而删除next指针指向的下个节点也就是倒数第n个节点。时间复杂度O(n)，空间复杂度O(1)。新建一个节点指向链表的头结点，这样当删除的节点是头结点也依然可行。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null)
return head;
ListNode result = new ListNode(0);
result.next = head;
ListNode fast = result;
ListNode slow = result;
for(int i = 1; i <= n + 1; i++){
fast = fast.next;
}
while(fast != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return result.next;
}
}
13. 725 分隔链表
- 从左到右链表的长度差不超过1，分三步，第一：计算链表的长度；第二：长度除以分组个数得到每组的链表长度，这样每组的链表长度一致；第三：长度对分组个数取余数，余数为剩余链表节点个数，均摊到第二部得到的每一组上，每一组分配一个节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode[] result = new ListNode[k];
int length = 0;
ListNode head = root;
while(head != null){
++length;
head = head.next;
}
int number = length / k;
int mod = length % k;
ListNode pre = root;
ListNode cur = root;
for(int i = 0; i < k; i++){
if (cur != null)
result[i] = cur;
int sum = number + (mod-- > 0 ? 1 : 0);
while(sum > 0){
pre = cur;
cur = cur.next;
--sum;
}
if(pre != null)
pre.next = null;
}
return result;
}
}
14. 61 旋转链表
- 方法一：通过栈解决，遍历一遍链表，计算链表长度，并将每一个节点放入栈中，并将尾结点和头节点相连接，然后通过右移位数对链表长度取余数为x，x意味着不管是循环几圈移动，最终结果相比较于开始状态，每个节点向右移动x个位置，则倒数第x个节点就是新的头结点。因此通过栈向外pop x+1 个节点，得到的就是头结点的前一个节点，通过此节点断开链表并得到头结点。时间复杂度是O(n)，空间复杂度也是O(n)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null)
return head;
Stack<ListNode> stack = new Stack<>();
ListNode cur = head;
int length = 0;
while(cur.next != null){
stack.push(cur);
cur = cur.next;
++length;
}
cur.next = head;
stack.push(cur);
++length;
int count = k % length;
while(count >= 0){
cur = stack.pop();
--count;
}
head = cur.next;
cur.next = null;
return head;
}
}
- 方法二：与方法一的思路一致，只不过由于用栈开销过大，其实不用栈也一样可以，计算出倒数第几个以后，链表长度减去倒数第几个，也就得到正数第几个数新链表的尾部，时间复杂度是O(n)，空间复杂度是O(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null)
return head;
ListNode tail = head;
int length = 0;
while(tail.next != null){
tail = tail.next;
++length;
}
tail.next = head;
++length;
int count = length - k % length;
while(count > 0){
tail = tail.next;
--count;
}
head = tail.next;
tail.next = null;
return head;
}
}
15. 1019 链表中的下一个更大节点
- 单调栈简介，顾名思义，单调栈就是一个从栈顶到栈底单调递减或者单调递增的栈。
- 方法：使用单调栈；题目要求找出比当前节点值大的第一个节点，注意是按顺序第一个，不是比当前节点大的值最小的节点；这个题的关键在于从前往后不方便，考虑从后往前，先遍历一遍链表，将值保存到ArrayList中方便从后往前遍历；然后用栈顶到栈底递增的单调栈保存当前节点以及比当前节点大的节点值，每次从后往前遍历链表的新节点，都比较当前遍历的节点值与栈顶节点值大小，将栈中比当前节点值小的节点都pop出去，那么此时栈顶的节点值就是比当前节点大的右端的第一个节点，并将当前节点入栈，由于比当前节点值小的节点都pop出去了，因此从右往左遍历下一个节点，大于其值得节点只能是栈中节点，因为栈中节点是当前节点的右边的节点(记为x)，以及比x大的节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] nextLargerNodes(ListNode head) {
if(head == null)
return new int[0];
ArrayList<Integer> arrayList = new ArrayList<>();
while(head != null){
arrayList.add(head.val);
head = head.next;
}
int[] result = new int[arrayList.size()];
Stack<Integer> stack = new Stack<>();
for(int i = arrayList.size() - 1; i >= 0; i--){
if(stack.empty()){
result[i] = 0;
stack.push(arrayList.get(i));
} else {
while(!stack.empty() && stack.peek() <= arrayList.get(i)){
stack.pop();
}
if(stack.empty()){
result[i] = 0;
stack.push(arrayList.get(i));
} else {
result[i] = stack.peek();
stack.push(arrayList.get(i));
}
}
}
return result;
}
}
15. 25 k个一组翻转链表
- 方法：先遍历一遍链表得到链表的长度，然后计算出k个一组共有x组，外层循环x次，内层循环每次循环遍历k个节点即每次将k个节点反转，并保持对上一次反转后的尾结点的访问，然后将上次访问的尾结点连接在当前反转后的头结点之前。时间复杂度O(n)，空间复杂度是O(1)。
/**
* 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) {
if(head == null || head.next == null || k == 1)
return head;
int length = 0;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = head;
ListNode next;
ListNode preTail = dummy;
while(cur != null){
++length;
cur = cur.next;
}
cur = head;
int number = length / k;
for(int i = 0; i < number; i++){
for(int j = 1; j < k; j++){
next = cur.next;
cur.next = next.next;
next.next = head;
head = next;
}
preTail.next = head;
preTail = cur;
head = cur.next;
cur = head;
}
return dummy.next;
}
}
16. 430 扁平化多级双向链表
- 方法一：题目要求对多级链表处理成一级的链表，通过递归的方式去处理，对于有子链表的节点，需要递归处理其子链表，将其子链表处理为一级；递归的返回值是处理之后的子链表的头结点；递归的终止条件是当前节点是空节点。这里需要优化的一个地方在于每次处理完一个子链表都要遍历一遍该子链表得到其尾结点，这个遍历比较浪费时间。时间复杂度是O(n)，空间复杂度是O(1)。
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
public Node() {}
public Node(int _val,Node _prev,Node _next,Node _child) {
val = _val;
prev = _prev;
next = _next;
child = _child;
}
};
*/
class Solution {
public Node flatten(Node head) {
Node cur = head;
Node next;
while(cur != null){
if(cur.child == null){
cur = cur.next;
}else {
next = cur.next;
cur.next = flatten(cur.child);
cur.next.prev = cur;
Node tail = cur.next;
while(tail.next != null){
tail = tail.next;
}
tail.next = next;
if (next != null)
next.prev = tail;
cur.child = null;
cur = next;
}
}
return head;
}
}
- 方法二：对方法一进行优化，当处理完子链表的同时通过全局变量得到处理后的子链表的尾结点，这样就不需要遍历子链表得到尾结点了，时间复杂度是O(n)，空间复杂度是O(1)。
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
public Node() {}
public Node(int _val,Node _prev,Node _next,Node _child) {
val = _val;
prev = _prev;
next = _next;
child = _child;
}
};
*/
class Solution {
private Node tail = null;
public Node flatten(Node head) {
Node cur = head;
Node next;
while(cur != null){
if(cur.child == null){
tail = cur;
cur = cur.next;
}else {
next = cur.next;
cur.next = flatten(cur.child);
cur.next.prev = cur;
if (next != null)
next.prev = tail;
tail.next = next;
cur.child = null;
cur = next;
if(cur != null)
tail = cur;
}
}
return head;
}
}
17. 1171 从链表中删去总和值为零的连续节点
- 前缀和：数组或者链表中或者其他线性存储数据结构中，从头部到当前位置的所有元素的和值，为当前元素的前缀和。
- 方法：类似于数组中的前缀和，前缀和是指从链表开头到当前节点的所有节点值的和，从链表开头开始遍历，如果两个不同节点的前缀和相等，则说明这两个节点之间的节点再加上这两个节点中位置靠后的节点值的和为0。在这个题目中就是可以删除的节点，把这些节点删除。如何记录前缀和呢，由于这里在不断地删除节点，考虑哈希表记录比较合适，HashMap比较合适，key为前缀和，value为当前节点。时间复杂度是O(n)，空间复杂度是O(n)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
int sum = 0;
HashMap<Integer, ListNode> hashMap = new HashMap<>();
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while(cur != null){
sum += cur.val;
if(hashMap.containsKey(sum)){
hashMap.get(sum).next = cur.next;
cur = cur.next;
}else {
hashMap.put(sum, cur);
cur = cur.next;
}
}
return dummy.next;
}
}
18. 138 复制带随机指针的链表
- 深拷贝与浅拷贝：在 Java 中，除了基本数据类型（元类型）之外，还存在 类的实例对象 这个引用数据类型。而一般使用 = 号做赋值操作的时候。对于基本数据类型，实际上是拷贝的它的值，但是对于对象这种引用类型而言，其实赋值的只是这个对象的引用，将原对象的引用传递过去，他们实际上还是指向的同一个对象。而浅拷贝和深拷贝就是在这个基础之上做的区分，如果在拷贝这个对象的时候，只对基本数据类型进行了拷贝，而对引用数据类型只是进行了引用的传递，而没有真实的创建一个新的对象，则认为是浅拷贝。反之，在对引用数据类型进行拷贝的时候，创建了一个新的对象，并且复制其内的成员变量，则认为是深拷贝。所以应该了解了，所谓的浅拷贝和深拷贝，只是在拷贝引用类型的时候，对 类的实例对象 这种引用数据类型的不同操作而已。
- 方法一：回溯法，题目要求对链表进行深拷贝，也就是创建新的节点并复制节点的值，而且这个链表特殊在存在随机指针，每个节点有两个指针，一个next一个random，需要对这个两个指针指向的下一个节点都进行复制，因此无法通过迭代遍历链表的方式去深拷贝，因为那样只能拷贝next或者random不能两者都深拷贝。即一个节点需要拷贝next指针指向的下一个节点，也需要拷贝random指针指向的节点，这每个节点就像是一个岔路口，next和random这两条路都需要遍历，这就是回溯来解决了，回溯可以遍历所有的可能路径。但是由于random指针的随机性，可能会导致random指针指向的节点是之前遍历过的，可能会导致无限循环，因此需要记录已经遍历的节点，如果已经遍历过了，该节点就不需要拷贝了只需要返回之前对这个节点的拷贝即可，因此需要记录遍历过的节点和其对应的拷贝节点，考虑用哈希表记录已经访问的节点，HashMap比较合适。时间复杂度O(n)，空间复杂度O(n)。
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
private HashMap<Node, Node> hashMap = new HashMap<>();
public Node copyRandomList(Node head) {
if(head == null)
return head;
Node node;
if(hashMap.containsKey(head)){
return hashMap.get(head);
} else {
node = new Node();
hashMap.put(head, node);
node.val = head.val;
node.next = copyRandomList(head.next);
node.random = copyRandomList(head.random);
}
return node;
}
}
- 方法二：迭代法，上面的回溯法中需要通过一个map来维护保存已经访问过的节点，空间复杂度是O(n)，可以优化空间复杂度，这个题给的链表实际上是一个标准的单向链表，然后每个节点增加了一个随机指针而已，因此不会出现random指向一个节点，而该节点不能通过next指针访问到。因此可以通过迭代的方式来完成复制，每次复制当前节点，并将访问过的节点维护在一个map中，key为访问过的原链表中节点value为访问过的原链表节点对应的复制的节点，如果random指针指向的节点在map中则返回其已复制的节点，否则新建一个节点进行复制；next指针同样。
- 上面解释了迭代法的过程，但是仍需要map，我们考虑如何去掉map？首先考虑map在这里的作用，map用于记录已访问的节点及其对应复制出的新节点的对应关系；其次考虑如何通过别的方式达到和map同样地记录这些信息的作用？可以将每一个节点都复制一个新节点，并保持新节点都在原节点之后，这样就和map一样的维护了key - value信息，map中通过get获取源节点对应的新节点，这里通过 源节点.next 获取源节点对应的新节点，同样的通过迭代的方式，复制每个节点的random指向关系和next指向关系，由于这里next指向关系有map的作用，因此应该先将所有random指向关系复制以后，再复制改变next指针的指向关系，防止失去类似map的key value信息。时间复杂度O(n)，空间复杂度O(1)。
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
if(head == null)
return null;
// 复制原链表，将复制出的新节点放在原节点之后
Node cur = head;
while(cur != null){
Node temp = new Node(cur.val);
temp.next = cur.next;
cur.next = temp;
cur = cur.next.next;
}
// 复制原链表中random指针的指向关系
cur = head;
while(cur != null){
cur.next.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
}
// 复制原链表中next指针的指向关系
cur = head;
Node result = cur.next;
Node curNew = head.next;
while(cur != null){
cur.next = curNew.next;
curNew.next = cur.next == null ? null : cur.next.next;
cur = cur.next;
curNew = curNew.next;
}
return result;
}
}
19. 109 有序链表转换二叉搜索树
- 二叉搜索树：首先是个二叉树，其次其每一个节点值均大于等于左子树所有节点值，小于等于右子树所有节点值。
- 二叉平衡搜索树：具有二叉搜索树的特点，其次其每个节点的左右子树深度差不超过1。
- 方法一：递归。由于链表是有序的，且递增，链表中间节点就是树的根节点，而中间节点左边的节点就可以递归的构成根节点的左子树，右边的节点递归构成根节点的右子树。
- 时间复杂度O(nlogn)。链表长度是N，则寻找其中间节点需要N/2时间复杂度，而对于第二次，会有两个长度为N/2的链表需要找到其中间节点，时间复杂度是2 * N / 4 = N / 2，第三次，会有四个长度为N/4的链表，4 * N / 8 = N / 2，由于每次都是对链表进行二分，则需要logN次二分，因此整体时间复杂度是logN * N / 2，即O(nlogn)。
- 空间复杂度O(logn)。因为使用递归的方法，所以需要考虑递归栈的空间复杂度。对于一棵非平衡二叉树，可能需要O(N)的空间，但是问题描述中要求维护一棵平衡二叉树，所以保证树的高度上界为O(logN)，因此递归调用栈的最大深度为O(logN)则空间复杂度为O(logN)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null)
return null;
return recursion(head);
}
private TreeNode recursion(ListNode head){
if(head == null)
return null;
if(head.next == null)
return new TreeNode(head.val);
// 找到中间节点，通过双指针快慢指针，满指针指向的节点就是中间节点
// 节点总数是奇数时，慢指针指向的刚好是中间节点
// 节点总数是偶数时，慢指针指向的刚好是中间两个节点中较后的节点，pre节点用于将链表断开
ListNode pre = head;
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
TreeNode treeNode = new TreeNode(slow.val);
treeNode.left = recursion(head);
treeNode.right = recursion(slow.next);
return treeNode;
}
}
- 方法二：方法一的主要问题是每次在找中间节点的时候，由于链表的访问特性，找中间节点需要线性时间复杂度，比较费时，如何优化这个寻找中间节点的操作？用空间换取时间。首先遍历链表，将链表转换为数组，然后仍通过递归的方式去构建二叉平衡搜索树，但是由于数组的访问速度是常数级别的，因此每次找中间节点的我们可以通过计算得到中间节点的索引，然后直接访问，使得找中间节点复杂度降低为O(1)，整体时间复杂度为O(n)，空间复杂度为O(n)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null)
return null;
int length = 0;
ListNode cur = head;
while(cur != null){
length++;
cur = cur.next;
}
int[] numbers = new int[length];
cur = head;
for(int i = 0; i < length; i++){
numbers[i] = cur.val;
cur = cur.next;
}
return recursion(numbers, 0, length - 1);
}
private TreeNode recursion(int[] numbers, int left, int right){
if(right < left)
return null;
// 找到中间节点
// 奇数找到的刚好是中间节点
// 偶数找到的是中间两个节点中较前者
int mid = left + ( right - left ) / 2;
TreeNode treeNode = new TreeNode(numbers[mid]);
treeNode.left = recursion(numbers, left, mid - 1);
treeNode.right = recursion(numbers, mid + 1, right);
return treeNode;
}
}
- 方法三：中序遍历，对二叉搜索树进行中序遍历的时候会得到一个升序列，而题目给的链表本身就是一个升序列，因此考虑中序遍历构造二叉搜索树，而方法一中先序遍历时需要首先花费时间找到中间节点访问中间节点得到树的根节点，而中序遍历就是从链表的第一个节点开始依次访问，因此不需要多花费时间去找链表的中间节点。同时也不需要像方法二中那样通过一个数组(额外的空间)来快速获取中间节点。时间复杂度为O(n)，空间复杂度是O(logN)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null)
return null;
int length = 0;
ListNode cur = head;
while(cur != null){
length++;
cur = cur.next;
}
this.head = head;
return recursion(0, length - 1);
}
private ListNode head;
private TreeNode recursion(int left, int right){
if(right < left)
return null;
// 找到中间节点
// 奇数找到的刚好是中间节点
// 偶数找到的是中间两个节点中较前者
int mid = left + ( right - left ) / 2;
TreeNode leftTree = recursion(left, mid - 1);
TreeNode treeNode = new TreeNode(this.head.val);
treeNode.left = leftTree;
this.head = this.head.next;
treeNode.right = recursion(mid + 1, right);
return treeNode;
}
}
20. 147 对链表进行插入排序
- 插入排序，以对数组进行插入排序举例，插入排序核心在于分为已有序数组和无序待排序元素组成的数组两部分，遍历无序元素组成的数组，对于当前遍历的元素在已经有序的数组中从头开始查找，直到找到一个元素的值大于当前遍历的元素记为x，则将当前遍历的元素插入x元素之前，否则就将当前遍历的元素放在有序数组的最后面，因为它是最大的。
- 方法：插入排序，利用插入排序的思想，链表分为两部分，一部分是有序的链表新建一个节点dummy为有序链表的头只用作记录头节点的位置，一部分是无序元素组成的链表，每次取无序元素组成的链表中的一个元素记为x，然后对已有序链表进行遍历，找到第一个大于x的元素，如果能找到则将x插在其前面，否则就将x插在整个链表的结尾。时间复杂度为O(n^2)，空间复杂度为O(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null || head.next == null)
return head;
// dummy记录已有序链表的头部位置
ListNode dummy = new ListNode(0);
// cur 用于遍历无序链表中的每一个元素
ListNode cur = head;
while(cur != null){
// 对于 cur所指向的元素，按照插入排序找到其应有的位置
ListNode next = cur.next;
ListNode tempCur = dummy;
while(tempCur.next != null && tempCur.next.val < cur.val){
tempCur = tempCur.next;
}
cur.next = tempCur.next;
tempCur.next = cur;
cur = next;
}
return dummy.next;
}
}
投递腾讯等公司8个岗位 >
用友开奖1人在聊