|
#Java、#链表、#双指针、#哈希表
一、今日学习链接
? ? ? ? 1、24.?Swap Nodes in Pairs，文章链接，视频链接
? ? ? ? 2、19.?Remove Nth Node From End of List，文章链接，视频链接
? ? ? ? 3、160.?Intersection of Two Linked Lists，文章链接
? ? ? ? 4、142.?Linked List Cycle II，文章链接，视频链接
二 、理论知识
三、解题思路
| 题号 | 思路 | 相关主题 | 难度 | | 24.?Swap Nodes in Pairs | dummy, dummy.next = head, cur = dummy while(cur.next != null && cur.next.next != null)（偶数个数、奇数个数，理解什么时候为空） 操作节点在被操作的两两节点之前 记录cue.next, cur.next.next.next（例如第三个节点） 技巧：画图演示，一目了然 | 链表 两两交换 | medium | | 19.?Remove Nth Node From End of List | 方法一：helper method 此题可以用上我们昨天学习的反转链表和删除链表元素，反转后n是正序，指针落在第n个节点之前，删除第n个节点即可，最后再反转过来 方法二：双指针 双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。->fast移动n+1步，fast、slow再同时移动，当fast为空，slow会停在被删除节点之前。 | 链表 反转链表 删除链表元素 双指针 | medium | | 160.?Intersection of Two Linked Lists | 方法一：HashSet 方法二：快慢指针 | 链表 哈希表(set) | easy | | 142.?Linked List Cycle II | HashSet | 链表 哈希表(set) | medium |
//19.删除链表的倒数第N个节点
//helper method，反转链表->删除第n个节点->再反转回来
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode reversed = reverse(head);
ListNode dummy = new ListNode(0);
ListNode prev = dummy;
dummy.next = reversed;
ListNode cur = reversed;
int i=1;
while(i<n) {
prev = cur;
cur = cur.next;
i++;
}
prev.next = cur.next;
ListNode res = reverse(dummy.next);
return res;
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
}
//19.删除链表的倒数第N个节点
//双指针：快慢指针解法
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
n++;
while (n-->0 && fast != null) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
四、总结????????
? ? ? ?链表问题，比如24.?Swap Nodes in Pairs，指针移动有先后顺序，可以画图来模拟指针移动，否则操作多个指针容易乱。L24非常考察链表基础的一题。
|