秋招力扣Hot100刷题总结——链表

• 题目要求：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
  
• 代码及思路
  • 遍历所有节点，将所有节点的next指向前一个节点
  • 由于要改变节点的next指向，而链表是单向的，因此需要使用一个节点变量先保存当前节点的next节点，然后再指向前一个节点
  • 代码

class Solution {public ListNode reverseList(ListNode head) {if(head==null||head.next==null)return head;ListNode pre=null;ListNode cur=head;while(head!=null){cur=head.next;head.next=pre;pre=head;head=cur;}return pre;}
}

• 题目要求：请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
  实现 LRUCache 类：
  LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
  函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
  
• 代码及思路
  • 使用双向链表进行实现，便于调整节点的位置
  • 需要注意的是还需要一个hashmap来存储关键字和节点的对应的关系，并且在相应的操作时不要忘记修改hashmap
  • 代码

class LRUCache {class DNode{int val;int key;DNode next;DNode pre;public DNode(){ }public DNode(int val,int key){this.val=val;this.key=key;}}DNode head;DNode tail;int size;int capacity;Map<Integer,DNode> cache=new HashMap<>();public LRUCache(int capacity) {head=new DNode();tail=new DNode();head.next=tail;tail.pre=head;this.capacity=capacity;size=0;}public int get(int key) {if(cache.containsKey(key)){DNode node=cache.get(key);moveToHead(node);return node.val;}return -1;}public void put(int key, int value) {if(cache.containsKey(key)){DNode node=cache.get(key);node.val=value;moveToHead(node);}else{DNode node=new DNode(value,key);cache.put(key,node);insertHead(node);size++;if(size>capacity){int lastKey=moveTail();cache.remove(lastKey);size--;}}}private void insertHead(DNode node){node.next=head.next;head.next.pre=node;head.next=node;node.pre=head;}private void moveToHead(DNode node){node.pre.next=node.next;node.next.pre=node.pre;insertHead(node);}private int moveTail(){int key=tail.pre.key;tail.pre=tail.pre.pre;tail.pre.next=tail;return key;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

• 题目要求：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
  
• 代码及思路
  • 先遍历两个链表，选择值小的节点加入合并后的链表
  • 当其中一个链表为空时结束循环，将不为空的链表剩下节点整个加入合并后的链表
  • 最好使用一个虚拟头接点，便于处理
  • 代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dumpy=new ListNode();ListNode cur=dumpy;while(list1!=null&&list2!=null){if(list1.val<=list2.val){cur.next=list1;list1=list1.next;}else{cur.next=list2;list2=list2.next;}cur=cur.next;}cur.next=list1==null?list2:list1;return dumpy.next;}
}

• 题目要求：给你一个链表的头节点 head ，判断链表中是否有环。
  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
  如果链表中存在环 ，则返回 true 。 否则，返回 false 。
  
• 代码及思路
  • 使用快慢指针解决问题，慢指针每次移动一步，快指针每次移动两步（相遇问题）
  • 当快慢指针相遇表明存在环
  • 代码

public class Solution {public boolean hasCycle(ListNode head) {ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast)return true;}return false;}
}

• 题目要求：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
  不允许修改 链表。
  
• 代码及思路
  • 本题是在找链表是否为环的基础上找出环的入口点
  • 在找环的过程中，当快慢指针相遇时慢指针从头开始，然后快指针和慢指针每次相同速度移动，下一次相遇的节点即为环入口（具体分析需要数学）
  • 代码

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){slow=head;while(slow!=null){if(slow==fast)return slow;slow=slow.next;fast=fast.next;}}}return null;}
}

• 题目要求：给你一个链表数组，每个链表都已经按升序排列。
  请你将所有链表合并到一个升序链表中，返回合并后的链表。
  
• 代码及思路
  • 采用逐个合并的方法，每次合并当前链表前已经合并的链表和当前链表
  • 代码

class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists.length==0)return null;if(lists.length==1)return lists[0];ListNode newHead=new ListNode();newHead.next=mergeTwo(lists[0],lists[1]);for(int i=2;i<lists.length;i++){newHead.next=mergeTwo(newHead.next,lists[i]);}return newHead.next;}private ListNode mergeTwo(ListNode l1,ListNode l2){ListNode dumpy=new ListNode();ListNode cur=dumpy;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?l1:l2;return dumpy.next;}
}

• 题目要求：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
  图示两个链表在节点 c1 开始相交：
  
• 代码及思路
  • 计算两个链表的长度，让较长的链表先走 (lengthA - lengthB) 步，这样两个链表就从同一节点开始遍历
  • 然后同时遍历两个链表，找到第一个相同的节点，即为相交节点
  • 代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA=headA;ListNode curB=headB;int l1=0;int l2=0;while(curA!=null){l1++;curA=curA.next;}while(curB!=null){l2++;curB=curB.next;}int move=Math.abs(l1-l2);curA=l1>l2?headA:headB;curB=l1>l2?headB:headA;while(move-->0){curA=curA.next;}while(curA!=null&&curB!=null){if(curA==curB)return curA;curA=curA.next;curB=curB.next;}return null;}
}

• 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
  
• 代码及思路
  • 使用快慢指针，快指针先移动n次
  • 然后快慢指针以相同速度每次移动一个节点一起移动，当快指针到达最后一个节点时，慢指针的next指向要被删除的节点，删除即可
  • 为了统一处理，使用一个虚拟节点
  • 代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dumpy=new ListNode();dumpy.next=head;ListNode slow=dumpy;ListNode fast=dumpy;while(n-->0){fast=fast.next;}while(fast.next!=null){slow=slow.next;fast=fast.next;}slow.next=slow.next.next;return dumpy.next;}
}

• 题目要求：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
  
• 代码及思路
  • 使用快排的思想，每次每次找到链表的中间节点，然后将链表分成两个子链表进行排序
  • 然后将两个排序后的子链表合并成一个链表（之前已经做过）
  • 代码

class Solution {public ListNode sortList(ListNode head) {if(head==null||head.next==null)return head;ListNode mid=findMid(head);ListNode rightHead=mid.next;mid.next=null;ListNode n1=sortList(head);ListNode n2=sortList(rightHead);return mergr(n1,n2);}private ListNode findMid(ListNode head){if(head==null||head.next==null){return head;}ListNode slow=head;ListNode fast=head.next.next;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}return slow;}private ListNode mergr(ListNode n1,ListNode n2){ListNode dumpy=new ListNode();ListNode cur=dumpy;while(n1!=null&&n2!=null){if(n1.val<=n2.val){cur.next=n1;n1=n1.next;}else{cur.next=n2;n2=n2.next;}cur=cur.next;}cur.next=n1!=null?n1:n2;return dumpy.next;}
}

• 题目要求：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
  请你将两个数相加，并以相同形式返回一个表示和的链表。
  你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
  
• 代码及思路
  • 遍历两个链表，每一次分别使用两个整数取出两个链表中节点值
  • 如果链表节点为空，则该整数值为0即可
  • 每次相加之后注意需要进位，因此当前结果值应该是两个链表节点值和上一节点和的进位之和与10取余
  • 最后注意两个链表都为空后还要看最后有没有进位
  • 代码

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {int c=0;ListNode dumpy=new ListNode();ListNode cur=dumpy;while(l1!=null||l2!=null){int a=0;int b=0;if(l1!=null){a=l1.val;l1=l1.next;}if(l2!=null){b=l2.val;l2=l2.next;}int num=(a+b+c)%10;c=(a+b+c)/10;ListNode node=new ListNode(num);cur.next=node;cur=cur.next;}if(c!=0){cur.next=new ListNode(c);}return dumpy.next;}
}