一、将两个有序链表合并为一个新的有序链表并返回
方法一：迭代
首先，我们设定一个哨兵节点 "prehead" ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前位置的值小于等于 l2 ，我们就把 l1 的值接在 prev 节点的后面同时将 l1 指针往后移一个。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都把 prev 向后移一个元素。
在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表。
/**
* 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 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;
}
}
方法二：递归
- 终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束
- 返回值：每一层调用都返回排序好的链表头
- 本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
二、给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
// 由于输入的列表已排序，因此我们可以通过将结点的值与它之后的结点进行比较来确定它是否为重复结点。如果它是重复的，我们更改当前结点的 next 指针，以便它跳过下一个结点并直接指向下一个结点之后的结点
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
while(current != null && current.next != null) {
if(current.val == current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
}
三、给定一个链表，判断链表中是否有环。
方法一：哈希表
我们遍历所有结点并在哈希表中存储每个结点。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）
方法二：快慢指针
首先创建两个不同速度的节点，如果两个节点相同时，则代表该链表是环形链表；
若不相同时，判断快指针当前节点/下一个节点是否到达终点(即null)，若为null则不是环形链表，否则移动节点
class Solution {
public boolean hasCycle(ListNode head) {
/// 1、哈希表
// Set<ListNode> map = new HashSet<>();
// while(head != null) {
// if(map.contains(head)) {
// return true;
// } else {
// map.add(head);
// }
// head = head.next;
// }
// return false;
/// 2、快慢指针
ListNode slow = head, fast = head.next;
while (slow != fast) {
if(fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
四、找到两个单链表相交的起始节点。
方法一、暴力遍历
对链表A中的每一个结点 a ，遍历整个链表 B 并检查链表 B 中是否存在结点和 a 相同。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/// 暴力遍历
while(headA != null) {
ListNode temp = headB;
while(temp != null) {
if(headA == temp) {
return headA;
} else {
temp = temp.next;
}
}
headA = headA.next;
}
return headA;
}
}
方法二、哈希表
遍历链表 A 并将每个结点存储在哈希表中。然后检查链表 B 中的每一个结点 b 是否在哈希表中。若在，则 b为相交结点
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/// 哈希表
Set<ListNode> set = new HashSet<>();
while(headA != null || headA.next != null) {
if(headB == null || headB.next == null) return null;
if(set.contains(headB)) {
return headB;
} else {
set.add(headA);
}
headA = headA.next;
headB = headB.next;
}
return headA;
}
}
方法三、双指针
- 创建两个指针 pA 和 pB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。
- 当 pA 到达链表的尾部时，将它重定位到链表 B 的头结点; 类似的，当 pB 到达链表的尾部时，将它重定位到链表 A 的头结点。
- 若在某一时刻 pA 和 pB 相遇，则 pA/pB 为相交结点。
- 想弄清楚为什么这样可行, 可以考虑以下两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于结点 9。 由于 B.length (=4) < A.length (=6)，pB 比 pA 少经过 2 个结点，会先到达尾部。将 pB 重定向到 A 的头结点，pApA 重定向到 B 的头结点后，pB 要比 pA 多走 2 个结点。因此，它们会同时到达交点。
- 如果两个链表存在相交，它们末尾的结点必然相同。因此当 pA/pB 到达链表结尾时，记录下链表 A/B 对应的元素。若最后元素不相同，则两个链表不相交。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/// 双指针
ListNode pA = headA, pB = headB;
while(pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
五、删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
这里需要注意的是：如果删除的节点位于链表的头部时 ，我们使用哨兵节点来解决该问题
- 初始化哨兵节点为 ListNode(0) 且设置 sentinel.next = head。
- 初始化两个指针 curr 和 prev 指向当前节点和前继节点。
- 当 curr != null：
- 比较当前节点和要删除的节点：
- 若当前节点就是要删除的节点：则 prev.next = curr.next。
- 否则设 prve = curr。
- 遍历下一个元素：curr = curr.next。
- 返回 sentinel.next。
注：哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们是纯功能的，通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode sentinel = new ListNode(0); // 哨兵节点，虚拟增加一个头结点
sentinel.next = head;
ListNode prev = sentinel, curr = head;
while (curr != null) {
if (curr.val == val) {
prev.next = curr.next;
} else {
prev = curr;
}
curr = curr.next;
}
return sentinel.next;
}
}
六、翻转链表
class Solution {
public ListNode reverseList(ListNode head) {
// 1、 迭代
// ListNode preHead = null;
// ListNode prev = head;
// while(prev != null) {
// ListNode temp = prev.next;
// prev.next = preHead;
// preHead = prev;
// prev = temp;
// }
// return preHead;
/// 2、 递归
if (head == null || head.next == null) return head;
ListNode temp = reverseList(head.next);
head.next.next = head;
head.next = null;
return temp;
}
}
七、请判断一个链表是否为回文链表。
先翻转链表 再比较
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head, prev = null, prepre = null;
while(fast != null && fast.next != null) {
/// 移动指针
prev = slow;
slow = slow.next;
fast = fast.next.next;
/// 翻转前半部链表
prev.next = prepre;
prepre = prev;
}
if(fast != null) { slow = slow.next;} // 链表为奇数，需要去除中间节点
// 遍历 对比
while (prev != null && slow != null) {
if (slow.val != prev.val) {
return false;
}
slow = slow.next;
prev = prev.next;
}
return true;
}
}
八、请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点
从链表里删除一个节点 node 的最常见方法是修改之前节点的 next 指针，使其指向之后的节点。
在这里我们无法访问我们想要删除的节点 之前 的节点，我们始终不能修改该节点的 next 指针。但是我们可以将想要删除的节点的值替换为它后面节点中的值，然后删除它之后的节点。
因为我们知道要删除的节点不是列表的末尾，所以我们可以保证这种方法是可行的。
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
九、给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
使用双指针，通过快慢指针找到中间点
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// fast != null && fast.next != null 用于找到第二个中间节点
// fast.next != null && fast.next.next != null 用于找到第一个中间节点
while( fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
十、给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
class Solution {
public int getDecimalValue(ListNode head) {
int sum = 0;
while (head != null) {
sum = sum * 2 + head.val;
head = head.next;
}
return sum;
}
}
注: 以上链表问题皆来源于https://leetcode-cn.com/problems/
网友评论