160.相交链表
哈希表：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> hashset = new HashSet<>();
ListNode temp = headA;
while(temp!=null){
hashset.add(temp);
temp = temp.next;
}
temp = headB;
while(temp != null){
if(hashset.contains(temp)){
return temp;
}
temp = temp.next;
}
return null;
}
}
时间复杂度：O(N)
空间复杂度：O(N)
双指针：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode p1 = headA;
ListNode p2 = headB;
while(p1 != p2){
p1 = p1==null?headB:p1.next;
p2 = p2==null?headA:p2.next;
}
return p1;
}
}
时间复杂度：O(N)
空间复杂度：O(1)
19.删除链表的倒数第N个节点
哈希表：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
HashMap<Integer,ListNode> hashmap = new HashMap<>();
int index = 0;
ListNode temp = head;
while(temp!=null){
hashmap.put(index,temp);
index++;
temp = temp.next;
}
int ans_index_before = index-n-1;
if(ans_index_before == -1){
return head.next;
}
ListNode remove_listnode = hashmap.get(ans_index_before);
remove_listnode.next = remove_listnode.next.next;
return head;
}
}
时间复杂度：O(N)
空间复杂度：O(N)
双指针(快慢指针)：
/**
* 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(0,head);
ListNode fast = dummy;
ListNode slow = dummy;
for(int i = 0;i<n;i++){
fast = fast.next;
}
while(fast.next!=null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
时间复杂度：O(N)
空间复杂度：O(1)
