今日任务
● 24. 两两交换链表中的节点
● 19.删除链表的倒数第N个节点
● 面试题 02.07. 链表相交
● 142.环形链表II
● 总结
详细布置
24. 两两交换链表中的节点
用虚拟头结点,这样会方便很多。
题目链接/文章讲解/视频讲解: https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
1)递归:不会写,学习
// 递归版本 class Solution { public ListNode swapPairs(ListNode head) { // base case 退出提交 if(head == null || head.next == null) return head; // 获取当前节点的下一个节点 ListNode next = head.next; // 进行递归 ListNode newNode = swapPairs(next.next); // 这里进行交换 next.next = head; head.next = newNode; return next; } }
2)双指针
/** * 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 swapPairs(ListNode head) { ListNode dummy = new ListNode(); dummy.next = head; ListNode pre = dummy; while (pre.next != null && pre.next.next != null){ ListNode temp = head.next; head.next = temp.next; temp.next = head; pre.next = temp; pre = head; head = pre.next; } return dummy.next; } }
19.删除链表的倒数第N个节点
双指针的操作,要注意,删除第N个节点,那么我们当前遍历的指针一定要指向 第N个节点的前一个节点,建议先看视频。
思路:开始看错题目,还以为是删除正数第N个
双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。
/** * 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 dummy = new ListNode(); dummy.next = head; ListNode fast = dummy; ListNode slow = dummy; for(int i = 0; i < n; i++){ fast = fast.next; } while(fast.next != null){ fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummy.next; } }
面试题 02.07. 链表相交
本题没有视频讲解,大家注意 数值相同,不代表指针相同。
思路:双指针,先遍历一遍看两个链表长度相差n,则快慢指针同时遍历,自己独立完成
/** * 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) { int countA = 0; int countB = 0; int n = 0; ListNode fast = headA;//假设A链表更长 ListNode slow = headB; while(fast != null){ fast = fast.next; countA++; } while(slow != null){ slow = slow.next; countB++; } if(countA - countB >= 0){ n = countA -countB; fast = headA; slow = headB; }else{ n = countB -countA; fast = headB; slow = headA; } for(int i = 0; i < n ;i++){ fast = fast.next; } while(fast != null){ if(fast == slow) return fast; else{ fast = fast.next; slow = slow.next; } } return null; }
142.环形链表II
算是链表比较有难度的题目,需要多花点时间理解 确定环和找环入口,建议先看视频。
题目链接/文章讲解/视频讲解:https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
思路:快慢指针,每次fast比slow多走一步,遍历,如果存在环,slow与fast相遇
在相遇节点处,定义一个指针index1,在头结点处定一个指针index2。
让index1和index2同时移动,每次移动一个节点, 那么他们相遇的地方就是 环形入口的节点。
标签:slow,ListNode,val,随想录,fast,next,链表,节点 From: https://www.cnblogs.com/gaoyuan2lty/p/16911973.html