1. 删除节点：
删除链表的倒数第N个节点：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { //快慢指针 ListNode fast = head; ListNode slow = head; //快指针先走n步 for(int i=0;i<n;i++){ fast = fast.next; } //如果快指针走了n步后为空，说明删除的是头节点 if(fast == null){ return head.next; } //当快指针不为空时，快慢一起走 while (fast.next != null) { fast = fast.next; slow = slow.next; } //走到快指针.next为空时，慢指针走到倒数第n个节点的前一个节点，跳过 slow.next = slow.next.next; return head; } }删除重复不保留：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
class Solution { public ListNode deleteDuplicates(ListNode head) { //不保留，需要新建链表暂存head if(head == null){ return null; } ListNode node = new ListNode(0); node.next = head; //从node开始 ListNode cur = node; while(cur.next != null && cur.next.next != null){ //如果相同，提取 if(cur.next.val == cur.next.next.val){ ListNode temp = cur.next; //判断后续重复 while(temp != null && temp.next != null && temp.val == temp.next.val){ temp = temp.next; } //直到跳过所有重复 cur.next = temp.next; }else{ cur = cur.next; } } return node.next; } }删除重复保留：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
class Solution { public ListNode deleteDuplicates(ListNode head) { if(head == null){ return null; } ListNode cur = head; while(cur != null && cur.next != null){ //如果相同，跳过 if(cur.val == cur.next.val){ cur.next = cur.next.next; }else{ cur = cur.next; } } return head; } }返回倒数第K个节点：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
class Solution { public ListNode getKthFromEnd(ListNode head, int k) { //快慢指针 if(head == null){ return null; } ListNode fast = head; ListNode slow = head; //快指针先走k步 for(int i=0;i<k;i++){ fast = fast.next; } //快慢一起走，直到快指针为null while(fast != null){ fast = fast.next; slow = slow.next; } return slow; } }
2. 合并链表：
合并K个有序链表：https://leetcode-cn.com/problems/merge-k-sorted-lists/
class Solution { public ListNode mergeKLists(ListNode[] lists) { //递归分成左右两个链表，合并链表 if(lists.length == 0){ return null; } return Merge(lists,0,lists.length-1); } public ListNode Merge(ListNode[] lists,int start,int end){ if(start == end){ return lists[start]; } int middle = start + (end - start)/2; ListNode l1 = Merge(lists,start,middle); ListNode l2 = Merge(lists,middle+1,end); return MergerSort(l1,l2); } public ListNode MergerSort(ListNode l1,ListNode l2){ //新建链表存储 ListNode node = new ListNode(0); ListNode cur = node; 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; } if(l1 != null){ cur.next = l1; } if(l2 != null){ cur.next = l2; } return node.next; } }
3. 翻转链表：
两两交换链表节点：https://leetcode-cn.com/problems/swap-nodes-in-pairs/
class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null){ return head; } //定义head的下一个节点为nextNode，指向head.next ListNode nextNode = head.next; //head翻转后它的下一个节点为nextNode.next的递归结果 head.next = swapPairs(nextNode.next); //最后再将nextNode.next指向head，拼接 nextNode.next = head; //返回nextNode return nextNode; } }K个一组翻转链表：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
class Solution { public ListNode reverseKGroup(ListNode head, int k) { //类型：翻转链表 //思路：每次for循环遍历到本次的第k个节点，翻转从head到cur的k个节点。递归从cur开始的下一组k个节点 //1. 递归出口：head == null || head.next == null //2. 单次过程：cur先提取head，for循环遍历k个节点，如果cur==null，返回head。 //3. node接收翻转从head到cur的结果 //4. head.next接收下一组k个翻转的结果 //5. 返回node给上一次递归 if(head == null || head.next == null){ return head; } ListNode cur = head; for(int i=0;i<k;i++){ if(cur == null){ return head; } cur = cur.next; } ListNode node = reverse(head,cur); head.next = reverseKGroup(cur,k); return node; } public ListNode reverse(ListNode head,ListNode cur){ ListNode pre = null; ListNode next = null; while(head != cur){ next = head.next; head.next = pre; pre = head; head = next; } return pre; } }翻转m到n的链表：https://leetcode-cn.com/problems/reverse-linked-list-ii/
class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if(head == null){ return null; } //需要对head进行操作，先新建链表存储 ListNode node = new ListNode(0); node.next = head; ListNode cur = node; //for循环到m节点的前一个节点 for(int i=1;i<m;i++){ cur = cur.next; } //提取m节点 ListNode M = cur.next; //翻转从m到n的节点 ListNode pre = null; ListNode next = null; for(int i=m;i<=n;i++){ next = M.next; M.next = pre; pre = M; M = next; } //拼接尾部 cur.next.next = next; //拼接头部 cur.next = pre; return node.next; } }翻转链表：https://leetcode-cn.com/problems/reverse-linked-list/
class Solution { public ListNode reverseList(ListNode head) { //双指针迭代 ListNode pre = null; ListNode next = null; while(head != null){ next = head.next; head.next = pre; pre = head; head = next; } return pre; //递归 if(head == null || head.next = null){ return head; } //尾递归到最后一个节点的前一个节点，因为递归出口，此时head为最后一个节点的前一个节点，head.next.next指向head，实现链表反转，head.next指向null防止断开 ListNode next = reverseList(head.next); head.next.next = head; head.next = null; return next; } }
4. 环形链表：
判断有无环：https://leetcode-cn.com/problems/linked-list-cycle/
public class Solution { public boolean hasCycle(ListNode head) { //快慢指针，快指针走2慢指针走1，判断能否相遇 if(head == null || head.next == null){ return false; } ListNode fast = head; ListNode slow = head; while(true){ //如果快指针走到尾部，返回false if(fast == null || fast.next == null){ return false; } fast = fast.next.next; slow = slow.next; //如果能相遇，break，返回true if(fast == slow){ break; } } return true; } }链表环入口：https://leetcode-cn.com/problems/linked-list-cycle-ii/
public class Solution { public ListNode detectCycle(ListNode head) { if(head == null || head.next == null){ return null; } //快慢指针，快指针走2，慢指针走1 ListNode fast = head; ListNode slow = head; while(true){ if(fast == null || fast.next == null){ return null; } fast = fast.next.next; slow = slow.next; if(fast == slow){ break; } } //重置快指针 fast = head; while(fast != slow){ fast = fast.next; slow = slow.next; } return slow; } }
京公网安备 11010502036488号