牛客算法top101
约 2161 字
预计阅读 5 分钟
次阅读
牛客算法top101
链表
BM1 反转链表
题目
- 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
- 链接
解答
- 步骤
- step 1：优先处理空链表，空链表不需要反转。
- step 2：我们可以设置两个指针，一个当前节点的指针，一个上一个节点的指针（初始为空）。
- step 3：遍历整个链表，每到一个节点，断开当前节点与后面节点的指针，并用临时变量记录后一个节点，然后当前节点指向上一个节点。
- step 4：再轮换当前指针与上一个指针，让它们进入下一个节点及下一个节点的前序节点。
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
//如果是空链表就直接返回
if(head==null){
return head;
}
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
ListNode temp = cur.next; //断开链表，要记录后续一个
cur.next = pre; //当前的next指向前一个
pre = cur; //前一个更新为当前
cur = temp; //当前更新为刚刚记录的后一个
}
return pre;
}
}
|
BM2 反转链表内指定区间
题目
- 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
- 链接
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
public class Solution {
/**
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here
ListNode pre=null;
ListNode cur=head;
for(int i=1; i<m;i++){
pre=cur;
cur=cur.next;
}
for(int i=m;i<n;i++){
//头插法
ListNode temp=cur.next;
cur.next=temp.next;
temp.next=pre.next;
pre.next=temp;
}
return head;
}
}
|
BM3 合并两个排序的链表
题目
解答
- 步骤
- 如果一个链表为空，直接返回另一个链表
- 两个链表的表头元素进行比较，将最小的加入到新链表
- 把剩下的链表的结点加入到新链表
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
//如果一个链表为空，直接返回另一个链表
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
//两个链表的表头元素进行比较，将最小的加入到新链表
ListNode head=new ListNode(0);
ListNode cur=head;
while(list1!=null&&list2!=null){
//比较两链表的首元素
if(list1.val<list2.val){
//把小的加入到新链表
cur.next=list1;
//list1往下
list1=list1.next;
}else{
cur.next=list2;
list2=list2.next;
}
//新链表往下
cur=cur.next;
}
//把剩下的链表的结点加入到新链表
if(list2!=null){
cur.next=list2;
}
if(list1!=null){
cur.next=list1;
}
return head.next;
}
}
|
BM4 判断链表是否有环
题目
解答
- 思路：使用快慢双指针遍历，如果快慢指针为null，说明无环，否则快指针迟早会追上慢指针，两者相遇，说明有环
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
/**
* 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) return false;
ListNode fast=head;
ListNode slow=head;
while(fast.next!=null&&fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
//相遇，说明有环
if(fast==slow){
return true;
}
}
//退出while,说明fast到链表尾遇到了null，无环
return false;
}
}
|
BM5 找出链表中环的入口
题目
解答
- 思路
- 步骤
- 使用判断链表中是否有环中的方法判断链表是否有环，并找到相遇的节点
- 慢指针继续在相遇节点，快指针回到链表头，两个指针同步逐个元素逐个元素开始遍历链表。
- 再次相遇的地方就是环的入口
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode hasCycle(ListNode head) {
if(head == null) //先判断链表为空的情况
return null;
ListNode fast = head; //快慢双指针
ListNode slow = head;
while(fast != null && fast.next != null){ //如果没环快指针会先到链表尾
fast = fast.next.next; //快指针移动两步
slow = slow.next; //慢指针移动一步
if(fast == slow) //相遇则有环，返回相遇的位置
return slow;
}
return null; //到末尾说明没有环，返回null
}
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode slow = hasCycle(pHead);
if(slow == null) //没有环
return null;
ListNode fast = pHead; //快指针回到表头
while(fast != slow){ //再次相遇即是环入口
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
|
BM6 链表中的倒数第k个节点
题目
- 一个长度为n的链表，返回原链表中从倒数第k个结点至尾节点的全部节点
- 如果该链表长度小于k，请返回一个长度为 0 的链表
- 链接
解答
- 思路：让两个指针一前一后，相隔刚好为k，这样，当快指针遍历到链表尾时，满指针刚好在倒数的第k个位置
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
ListNode fast=pHead;
ListNode slow=pHead;
//先让快指针走到顺数第k个位置
for(int i=0;i<k;i++){
if(fast!=null){
fast=fast.next;
}else{
//没有到第k个位置就为空了，说嘛链表长度小于k，返回null
return null;
}
}
//slow、fast一起往下走，当fast走到底时，slow指向倒数第k个
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
|
标题
题目
解答