记录一下最近刷的比较有意思的题
1. 环形链表
给定一个链表，判断链表中是否有环。
进阶
你能否不使用额外空间解决此题？
我的思路与解答（1ms）：
首先理解环形链表的概念，我开始以为只有一种，就是头尾相连的链表就是环形链表，如下图；
图1
但其实还有一种比较特殊一点的环形链表，如下图；
图2
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution {
public boolean hasCycle(ListNode head) {
if(head == null) return false;
/**
* 主要思路：用双指针解法，slow和fast，都从头部开始
* slow每次走一步，fast每次走两步
* 这样不论是头尾相连的环形链表还是特殊的环形链表
* 在若干步后slow和fast会相遇
*/
ListNode slow = head;
ListNode fast = head;
while(fast.next != null){
slow = slow.next;
fast = fast.next;
if(fast.next != null){
fast = fast.next;
}else{
return false;
}
if(slow.equals(fast)){
return true;
}
}
return false;
}
}
小结：
一开始只想到了头尾相连的链表，去搜索了相关概念后才知道原来还有另一种，但是这题做起来思路还是比较明确。
2. 合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入: 1->2->4, 1->3->4
输出: 1->1->2->3->4->4
我的思路与解答（11 ms）：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null) return null;
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode head;
ListNode p1;
ListNode p2;
ListNode temp;
// 首先对比两个链表头部的值的大小，小的链表为最终返回的链表，即将头部大的拆开插入小的链表
if(l1.val <= l2.val){
head = l1;
p1 = l1;
p2 = l2;
}else{
head = l2;
p1 = l2;
p2 = l1;
}
/**
* 进入循环，当判断p2指向的结点的值大于等于p1所指向且小于p1的下个结点的值时
* 将p2所指向的结点插到p1之后，并将p1指向被插入的结点
* 当p1或p2为最后一个结点时跳出循环
*/
while(p1.next != null && p2.next != null){
if(p2.val >= p1.val) {
if(p1.next.val > p2.val) {
temp = p1.next;
p1.next = p2;
l2 = p2.next;
p2.next = temp;
p1 = p2;
p2 = l2;
continue;
}
p1 = p1.next;
}
}
/**
* 这时会有两张情况：
* 1. p2为最后一个结点，只需再进行一次循环，将p2插入链表
* 2. p1为最后一个结点，说明链表的最大的值都没有比p2所指向的结点的值大，只需将p2插到链表的最后即可
* 因为这时p1指向的是最后一个结点，所以直接 p1.next = p2 即可
*/
if(p2.next == null){
while(p1.next != null){
if(p2.val >= p1.val){
if(p1.next.val > p2.val) {
temp = p1.next;
p1.next = p2;
l2 = p2.next;
p2.next = temp;
p1 = p2;
p2 = l2;
return head;
}
p1 = p1.next;
}
}
}
if(p1.next == null){
p1.next = p2;
}
return head;
}
}
小结：
这题第一次做的时候思路很乱，做了一个晚上都没做出来，第二天再做的时候理清思路10分钟就做出来了，事实证明做题思路很重要
3. 总结
链表类的题目尤其需要思路明确，有一点错误就容易发生空指针异常。
本文作者：RoNnx
博客链接：http://ronnx.top/2018/06/17/20180004/
版权声明：本作品采用「知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可」,转载请注明出处！
网友评论