力扣--链表算法
删除中间点内容示例代码复杂度
二进制链表转整数内容示例代码复杂度
返回倒数第K个节点内容示例代码复杂度
从尾到头打印链表内容示例代码复杂度
链表的中间结点内容示例复杂度
移除重复节点内容示例代码复杂度
反转链表内容示例代码复杂度
合并两个有序链表内容示例代码复杂度
链表相交内容示例代码复杂度
链表中的下一个更大节点内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
内容示例代码复杂度
删除中间点
内容
实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。
示例
输入：单向链表a->b->c->d->e->f中的节点c 结果：不返回任何数据，但该链表变为a->b->d->e->f
代码
class Solution {
public void deleteNode(ListNode node
) {
node
.val
= node
.next
.val
;
node
.next
= node
.next
.next
;
}
}
复杂度
时间复杂度：O(1)。 空间复杂度：O(1)。
二进制链表转整数
内容
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值 。
示例
输入：head = [1,0,1] 输出：5 解释：二进制数 (101) 转化为十进制数 (5)
代码
class Solution {
public int getDecimalValue(ListNode head
) {
ListNode cur
= head
;
int ans
= 0;
while(cur
!= null
){
ans
= ans
* 2 + cur
.val
;
cur
= cur
.next
;
}
return ans
;
}
}
复杂度
时间复杂度：O(N)，其中N是链表中的节点个数。 空间复杂度：O(1)。
返回倒数第K个节点
内容
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
示例
输入： 1->2->3->4->5 和 k = 2 输出： 4
代码
class Solution {
public int kthToLast(ListNode head
, int k
) {
if(k
<= 0 || head
== null
){
return 0;
}
ListNode fast
= head
;
ListNode slow
= head
;
while(k
- 1 > 0){
fast
= fast
.next
;
k
--;
}
while(fast
!= null
&& fast
.next
!= null
){
slow
= slow
.next
;
fast
= fast
.next
;
}
return slow
.val
;
}
}
复杂度
时间复杂度 O(N) :N为链表长度。 空间复杂度 O(1)。
从尾到头打印链表
内容
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例
输入：head = [1,3,2] 输出：[2,3,1]
代码
class Solution {
public int[] reversePrint(ListNode head
) {
Stack
<ListNode> stack
= new Stack<ListNode>();
ListNode node
= head
;
while(node
!= null
){
stack
.push(node
);
node
= node
.next
;
}
int size
= stack
.size();
int[] print
= new int[size
];
for(int i
= 0;i
< size
;i
++){
print
[i
] = stack
.pop().val
;
}
return print
;
}
}
复杂度
时间复杂度：O(n)正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。 空间复杂度：O(n)额外使用一个栈存储链表中的每个节点。
链表的中间结点
内容
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例
输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
class Solution {
public ListNode
middleNode(ListNode head
) {
ListNode slow
= head
;
ListNode fast
= head
;
while(fast
!= null
&& fast
.next
!= null
){
slow
= slow
.next
;
fast
= fast
.next
.next
;
}
return slow
;
}
}
复杂度
时间复杂度：O(N)O(N)，其中 NN 是给定链表的结点数目。 空间复杂度：O(1)O(1)，只需要常数空间存放 slow 和 fast 两个指针。
移除重复节点
内容
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例
输入：[1, 2, 3, 3, 2, 1] 输出：[1, 2, 3]
代码
class Solution {
public ListNode
removeDuplicateNodes(ListNode head
) {
if(head
== null
){
return head
;
}
Set
<Integer> occurred
= new HashSet<Integer>();
occurred
.add(head
.val
);
ListNode pos
= head
;
while(pos
.next
!= null
){
ListNode cur
= pos
.next
;
if(occurred
.add(cur
.val
)){
pos
= pos
.next
;
}else{
pos
.next
= pos
.next
.next
;
}
}
pos
.next
= null
;
return head
;
}
}
复杂度
时间复杂度：O(N)，其中 N 是给定链表中节点的数目。 空间复杂度：O(N)。在最坏情况下，给定链表中每个节点都不相同，哈希表中需要存储所有的 N 个值。
反转链表
内容
反转一个单链表。
示例
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
代码
class Solution {
public ListNode
reverseList(ListNode head
) {
ListNode prev
= null
;
ListNode curr
= head
;
while(curr
!= null
){
ListNode nextTemp
= curr
.next
;
curr
.next
= prev
;
prev
= curr
;
curr
= nextTemp
;
}
return prev
;
}
}
复杂度
时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。 空间复杂度：O(1)。
合并两个有序链表
内容
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
代码
class Solution {
public ListNode
mergeTwoLists(ListNode l1
, ListNode l2
) {
ListNode prehead
= new ListNode(-1);
ListNode prev
= prehead
;
while(l1
!= null
&& l2
!= null
){
if(l1
.val
<= l2
.val
){
prev
.next
= l1
;
l1
= l1
.next
;
}else{
prev
.next
= l2
;
l2
= l2
.next
;
}
prev
= prev
.next
;
}
prev
.next
= l1
== null
? l2
: l1
;
return prehead
.next
;
}
}
复杂度
时间复杂度：O(n + m)O(n+m) ，其中 nn 和 mm 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)O(n+m)。
空间复杂度：O(1)O(1) 。我们只需要常数的空间存放若干变量。
链表相交
内容
给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
示例
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
代码
public class Solution {
public ListNode
getIntersectionNode(ListNode headA
, ListNode headB
) {
ListNode t1
= headA
;
ListNode t2
= headB
;
while(t1
!= t2
){
t1
= t1
!= null
? t1
.next
: headB
;
t2
= t2
!= null
? t2
.next
: headA
;
}
return t2
;
}
}
复杂度
链表中的下一个更大节点
内容
给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, … 。 每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。 返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。 注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
示例
输入：[2,1,5] 输出：[5,5,0]
代码
class Solution {
public int[] nextLargerNodes(ListNode head
) {
int[] arr
= new int[10000];
int[] valueArr
= new int[10000];
Stack
<Integer> stack
= new Stack<>();
int length
= 0;
int value
;
while(head
!= null
){
value
= head
.val
;
valueArr
[length
] = value
;
while(!stack
.isEmpty() && value
> valueArr
[stack
.peek()]){
arr
[stack
.pop()] = value
;
}
stack
.add(length
);
length
++;
head
= head
.next
;
}
int[] result
= new int[length
];
for(int i
= 0;i
< length
; i
++){
result
[i
] = arr
[i
];
}
return result
;
}
}
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
内容
示例
代码
复杂度
