牛客每日一题
链表：
4月23日
描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
示例1：
输入：{1,2,3}
输出：{3,2,1}
示例2：
输入：{}
输出：{}
说明：空链表则输出空
题解代码：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public ListNode ReverseList(ListNode head) {
//新链表
ListNode newHead = null;
while (head != null) {
//先保存访问的节点的下一个节点，保存起来
//留着下一步访问的
ListNode temp = head.next;
//每次访问的原链表节点都会成为新链表的头结点，
//其实就是把新链表挂到访问的原链表节点的
//后面就行了
head.next = newHead;
//更新新链表
newHead = head;
//重新赋值，继续访问
head = temp;
}
//返回新链表
return newHead;
}
4月24日
描述
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0≤n*≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)
如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
示例1：
输入：{1,3,5},{2,4,6}
输出：{1,2,3,4,5,6}
示例2：
输入：{},{}
输出：{}
示例3：
输入：{-1,2,4},{1,3,4}
输出：{-1,1,2,3,4,4}
题解代码：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
// list1 list2为空的情况
if(list1 == null || list2 == null){
return list1 != null ? list1 : list2;
}
// 两个链表元素依次对比
if(list1.val <= list2.val){
// 递归计算 list1.next, list2
list1.next = Merge(list1.next, list2);
return list1;
}else{
// 递归计算 list1, list2.next
list2.next = Merge(list1, list2.next);
return list2;
}
}
}
4月25日
描述
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
示例1:
输入：{1,2,3,4,5},2
输出：{4,5}
说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。
示例2：
输入：{2},8
输出：{}
题解代码：
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
if (pHead == null || k == 0){
return null;
}
Stack<ListNode> stack = new Stack<>();
//链表节点压栈
while (pHead != null) {
stack.push(pHead);
pHead = pHead.next;
}
// 判断栈的元素是否小于k
if (stack.size() < k){
return null;
}
//在出栈串成新的链表
ListNode firstNode = stack.pop();
while (--k > 0) {
// 将出栈的元素重新连接成为链表
ListNode temp = stack.pop();
temp.next = firstNode;
firstNode = temp;
}
return firstNode;
}
}
4月26日
描述
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
输入描述
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
返回值描述：
返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。
示例1：
输入：{1,2,3},{4,5},{6,7}
输出：{6,7}
说明：第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的
示例2：
输入：{1},{2,3},{}
输出：{}
说明：2个链表没有公共节点 ,返回null，后台打印{}
题解代码：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1,l2 = pHead2;
while(l1 != l2){
l1 = (l1 == null)?pHead2 : l1.next;
l2 = (l2 == null)?pHead1 : l2.next;
}
return l1;
}
}
4月27日
描述
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→21→1→2,返回1→21→2.
给出的链表为1→1→2→3→31→1→2→3→3,返回1→2→3.
示例1：
输入：{1,1,2}
输出：{1，2}
示例2：
输入：{}
输出：{}
题解代码：
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode deleteDuplicates (ListNode head) {
// write code here
if(head == null){
return null;
}
ListNode cur = head;
while(cur!= null && cur.next != null){
if(cur.val == cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
}
4月28日
描述
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
示例1：
输入：{1}
输出：true
示例2：
输入：{2,1}
输出：true
说明：2->1
示例3：
输入：{1,2,2,1}
输出：true
说明：1->2->2->1
题解代码：
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
// write code here
if(head.next == null){
return true;
}
List<Integer> nums = new ArrayList<>();
while(head != null){
nums.add(head.val);
head = head.next;
}
int left = 0;
int right = nums.size() - 1;
while(left < right){
if(!nums.get(left).equals(nums.get(right))){
return false;
}
++left;
--right;
}
return true;
}
}
4月29日
描述
判断给定的链表中是否有环。如果有环则返回true，否则返回false。
输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：
可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。
示例1：
输入：{3,2,0,-4},1
输出：true
说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true
示例2：
输入：{1},-1
输出：false
说明：第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
示例3：
输入：{-1,-7,7,-4,19,6,-9,-5,-2,-5},6
输出：true
题解代码：
/**
* 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 pos = head;
// 哈希表记录访问过的结点
Set<ListNode> visited = new HashSet<ListNode>();
while (pos != null) {
// 判断结点是否被访问
if (visited.contains(pos)) {
return true;
} else {
// 结点记录添加到哈希表中
visited.add(pos);
}
// 遍历
pos = pos.next;
}
return false;
}
}
4月30日
描述
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：
可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
输入描述：
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述：
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
示例1：
输入：{1,2},{3,4,5}
输出：3
说明：返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
示例2：
输入：{1},{}
输出："null"
说明：没有环，返回对应编程语言的空结点，后台程序会打印"null"
题解代码：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead == null) return null;
// 定义快慢指针
ListNode slow = pHead;
ListNode fast = pHead;
while(fast != null && fast.next != null){
// 快指针是满指针的两倍速度
fast = fast.next.next;
slow = slow.next;
// 记录快慢指针第一次相遇的结点
if(slow == fast) break;
}
// 若是快指针指向null，则不存在环
if(fast == null || fast.next == null) return null;
// 重新指向链表头部
fast = pHead;
// 与第一次相遇的结点相同速度出发，相遇结点为入口结点
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
