【Java】HOT100 链表
代码随想录的链表题在这里:
目录
HOT 100:链表
LeetCode160:相交链表
思路:先计算两个链表的长度,让两个指针cur1,cur2指向对齐的位置,然后再遍历比较直到cur1==cur2,返回cur1。秒了。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int num1 = 0,num2 = 0;
ListNode cur1 = headA;
ListNode cur2 = headB;
while(cur1 != null){
cur1 = cur1.next;
num1++;
}
while(cur2 != null){
cur2 = cur2.next;
num2++;
}
cur1 = headA;
cur2 = headB;
if(num1>num2){
for(int i=0;i<Math.abs(num1-num2);i++){
cur1 = cur1.next;
}
}else{
for(int i=0;i<Math.abs(num1-num2);i++){
cur2 = cur2.next;
}
}
while(cur1 != null){
if(cur1 == cur2){
return cur1;
}else{
cur1 = cur1.next;
cur2 = cur2.next;
}
}
return cur1;
}
}
LeetCode206:反转链表
思路:第一步肯定是看cur是否为空;接着利用pre和cur双指针来反转链表;其中用到一个临时指针tmp来记录cur的下一个节点。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
if(cur == null){
return pre;
}
while(cur!=null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
LeetCode206:回文链表
思路:用栈来写比较巧妙,前半部分入栈,比较出栈和下半部分即可;
注意要区分奇数和偶数,奇数个时,要跳过中间的数再比较
class Solution {
public boolean isPalindrome(ListNode head) {
int len = 0;
ListNode cur = head;
Stack<ListNode> stack = new Stack<>();
while(cur != null){
cur = cur.next;
len++;
}
cur = head;
for(int i=0;i<len/2;i++){
stack.push(cur);
cur = cur.next;
}
if(len%2 != 0) cur = cur.next;
for(int i=0;i<len/2;i++){
if(cur.val != stack.pop().val){
return false;
}
cur = cur.next;
}
return true;
}
}
LeetCode141:环形链表
思路:判断是否有环:快慢指针法,快指针走两步,慢指针走一步,判断是否会相遇;
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast.next!=null && fast!=null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
return true;
}
}
return false;
}
}
LeetCode142:环形链表ii
思路:分两步,秒了
(1)判断是否有环:快慢指针法,快指针走两步,慢指针走一步,判断是否会相遇;
(2)如果有环,从哪里开始入环。根据一些数学运算可知,当n=1时,x=z,即从头结点和相遇节点出发,以同样每次走一个节点的速度,二者将在环形出口节点相遇。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
ListNode index1 = head;
ListNode index2 = slow;
while(index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
LeetCode21:合并两个有序列表
用到虚拟头结点、pre和cur1、cur2对比,分为三种情况
(1)cur1、cur2都不为null时,选择较小的一个作为下一个节点
(2)cur1为null,把pre的下一个节点设为cur2;反之也是一样
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//为了不单独考虑头结点的情况,创建虚拟头结点
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
ListNode cur1 = list1;
ListNode cur2 = list2;
while(cur1 != null && cur2 != null){
if(cur1.val>cur2.val){
pre.next = cur2;
pre = cur2;
cur2 = cur2.next;
}else{
pre.next = cur1;
pre = cur1;
cur1 = cur1.next;
}
}
if(cur1 == null){
pre.next = cur2;
}
if(cur2 == null){
pre.next = cur1;
}
return dummy.next;
}
}
LeetCode2:两数相加
思路:自己写的,不一定最优
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode cur1 = l1;
ListNode cur2 = l2;
int num1 = 0, num2 = 0;
int sum1 = 0, sum2 = 0;
while(cur1 != null){
sum1 += cur1.val*Math.pow(10, num1);
cur1 = cur1.next;
num1++;
}
while(cur2 != null){
sum2 += cur2.val*Math.pow(10, num2);
cur2 = cur2.next;
num2++;
}
int sum = sum1 + sum2;
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
if(sum==0) return new ListNode(0);
while(sum != 0){
int n = sum % 10;
sum = sum/10;
ListNode tmp = new ListNode(n);
pre.next = tmp;
pre = tmp;
}
return dummy.next;
}
}
LeetCode2:两数相加
思路:删除倒数第n个节点,利用快慢指针的差值;要删除倒数第n个节点,就要让指针指向它的前一个节点(倒数第n+1个节点)。秒。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1,head);
ListNode slow = dummy;
ListNode fast = dummy;
for(int i=0;i<=n;i++){
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
//当fast指向null时,slow指向倒数第n+1个节点
slow.next = slow.next.next;
return dummy.next;
}
}
LeetCode24:两两交换链表中的节点
思路:还是pre当dummy,设cur1,cur2两两交换,记得设置临时指针tmp用于记录第三个节点
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1,head);
ListNode pre = dummy;
ListNode cur1;
ListNode cur2;
ListNode tmp;
while(pre.next!= null && pre.next.next != null){
cur1 = pre.next;
cur2 = pre.next.next;
tmp = pre.next.next.next;
pre.next = cur2;
cur2.next = cur1;
cur1.next = tmp;
pre = cur1;
}
return dummy.next;
}
}
LeetCode25:K个一组反转链表
思路:两个递归
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || head.next == null) return head;
ListNode tail = head;
for(int i=0;i<k;i++){
if(tail == null){
//不翻转直接返回
return head;
}
tail = tail.next; //这里可以看出是左闭右开区间
}
ListNode newHead = reverse(head,tail);
head.next = reverseKGroup(tail,k);
return newHead;
}
public ListNode reverse(ListNode head, ListNode tail){
ListNode pre = null;
ListNode cur = head;
while(cur != tail){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
LeetCode138:随机链表的复制
思路:三个步骤:复制-random-拆分
class Solution {
public Node copyRandomList(Node head) {
if(head==null)
{
return null;
}
Node cur1=head;
//复制, 相当于1->2->3 ==> 1->1'->2->2'->3->3'
while(cur1!=null)
{
Node temp1=new Node(cur1.val);
temp1.next=cur1.next;
cur1.next=temp1;
cur1=temp1.next;
}
//随机指向
Node cur2=head;
while(cur2!=null)
{
Node temp2=cur2.next; //tmp2即复制节点
if(cur2.random!=null)
{
temp2.random=cur2.random.next; //random节点的next就是复制random
}
cur2=temp2.next;
}
//拆分原链表和拷贝链表
Node cur3=head;
Node result=head.next;
while(cur3.next!=null)
{
Node temp3=cur3.next;
cur3.next=temp3.next;
cur3=temp3;
}
return result;
}
}
LeetCode148:排序链表
链表排序和数组排序最天然的不同在于访问元素与交换元素的成本,类似冒泡等排序方法就基本用不起来了,因为访问和交换的开销太大。链表排序方法主要有以下三种:
● 归并排序:链表最佳排序方法,注意要先递归链表的右半部,对链表进行截断,再递归链表的左半部。
● 快速排序:元素无法直接进行交换,可以每次遍历将链表分为大小两个部分分别存储到两个子链表中(实际上只需要构建一个新链表),再进行合并。
● 堆排序:简单粗暴,当空间复杂度不符合要求。
思路:
1. 先用fast和slow双指针法找到链表的中点(奇数链表为中点,偶数链表为中点的左面一个)
2. 然后从中点处递归断链,直到终止条件:一个节点指向nul
3. 合并(先while比较,再接剩下的多余的链)
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode slow = head;
ListNode fast = head;
//快慢指针找中点,奇数找中点,偶数找中点左边的一个
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
//slow.next就是第二段的头结点
ListNode l1 = sortList(slow.next);
slow.next = null;
ListNode l2 = sortList(head);
//接着合并连接新链表
ListNode newHead = new ListNode(-1);
ListNode cur = newHead;
while(l1 != null && l2 != null){
if(l1.val<l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null? l2:l1;
return newHead.next;
}
}
LeetCode23:合并K个升序链表
思路:利用PriorityQueue构建小根堆,把节点加进去会自动升序排列好
类似的题目还有:347. 前K个高频元素,解析见链表02
相比于只加入头结点之后再比较,总感觉全部加入更加快速些。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(null == lists || lists.length == 0){
return null;
}
ListNode newHead = new ListNode(-1);
ListNode cur = newHead;
//构建小根堆,
PriorityQueue<ListNode> pq = new PriorityQueue<>((o1,o2)->(o1.val - o2.val));
//先把节点全部加入到小根堆中
for(ListNode head : lists){
while(head!= null){
pq.add(head);
head = head.next;
}
}
while(!pq.isEmpty()){
ListNode tmp = pq.poll();
//弹出的第一个 就是最小的头节点。
cur.next = tmp;
//指针不断移动。
cur = cur.next;
}
return newHead.next;
}
}
LeetCode146:LRU(最近最少使用)缓存
思路:双向链表(每个节点包括key,value和前后指针prev和next)+哈希map(key-node)
首先对于LRUCache类,
要先定义双向链表的节点,以及以capacity初始化LRU缓存
Map<Integer,ListNode>
get函数:如果存在则从map里获得node.value,把node移到链表最前方(刚刚使用过)
put函数:如果存在则node.val = value,然后移动node到最前方
不存在则新建node加入map,移动node到最前方,size++;
(当size>capacity,再size--,删去链表末段的节点,并从map移除节点)
public class LRUCache {
//定义双向链表,靠近头的是最近使用的,靠近尾的是最久未使用的。
//定义HashMap,存储链表节点信息
class LinkNode {
int key;
int value;
LinkNode prev;
LinkNode next;
public LinkNode() {}
public LinkNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, LinkNode> map = new HashMap<>();
private int size;
private int capacity;
private LinkNode head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
head = new LinkNode();
tail = new LinkNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
LinkNode node = map.get(key);
if (node == null) {
return -1; //不存在返回-1
}
//存在需移动位置至链表头部
moveNodeToHead(node);
return node.value;
}
public void put(int key, int value) {
LinkNode node = map.get(key);
if (node != null) {
node.value = value;
//node移动位置至链表头部
moveNodeToHead(node);
} else {
LinkNode n = new LinkNode(key, value);
map.put(key, n);
//新node添加至链表头部
addHead(n);
size++;
if (size > capacity) {
//逐出最久未使用的node
rmTailNode();
size--;
}
}
}
private void moveNodeToHead(LinkNode node) {
removeNode(node); //删除节点
addHead(node); //添加至头节点
}
private void rmTailNode() {
map.remove(tail.prev.key);
removeNode(tail.prev);
}
private void removeNode(LinkNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addHead(LinkNode node) {
head.next.prev = node;
node.prev = head;
node.next = head.next;
head.next = node;
}
}
原文地址:https://blog.csdn.net/weixin_43562105/article/details/137747241
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!