合并两个有序链表，回文链表，环形链表
合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路
迭代顺序比较两个链表的大小
代码
/**
* 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) {
ListNode soldier = new ListNode(0); //利用哨兵结点简化实现难度 技巧三
ListNode p = soldier;
while ( l1 != null && l2 != null ){
if ( l1.val < l2.val ){
p.next = l1;
l1 = l1.next;
}
else{
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null) { p.next = l1; }
if (l2 != null) { p.next = l2; }
return soldier.next;
}
}
[题目来源]https://leetcode-cn.com/problems/merge-two-sorted-lists/
回文链表
请判断一个链表是否为回文链表。
输入: 1->2->2->1
输出: true
思路
- 寻找中间节点
- 根据中间节点反转后半部分链表
- 比较两个链表的值是否相等
- 还原链表
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) return true;
//寻找中间节点
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) result = false;
p1 = p1.next;
p2 = p2.next;
}
// 复原链表
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
// 反转链表
private 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;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
[题目来源]https://leetcode-cn.com/problems/linked-list-cycle/
环形链表
给定一个链表，判断链表中是否有环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例：
输入：head = [3,2,0,-4], pos = 1
输出：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) {
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next !=null) {
slow = slow.next;
fast = fast.next.next;
if(fast == slow){return true;}
}
return false;
}
}