算法记录lday4 LinkedList链表交换 删除倒数N个点 环形链表

今日任务

● 24. 两两交换链表中的节点
● 19.删除链表的倒数第N个节点
● 面试题 02.07. 链表相交
● 142.环形链表II

两两交换链表中的节点

题目描述

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)
Swapping nodes in a linked list in pairs

link

https://leetcode.com/problems/swap-nodes-in-pairs/description/

思路 solution

difficult one
if you want to swap two node
you have to use one pointer pointer to the node before the first node of two nodes

处理两个节点
Handle two nodes
需要面对四个节点
Need to face four nodes

the node before these two nodes
the node after these two nodes

difficult two
when will the cur node stop
when the cur.next == null or cur.next.next == null
the while loop会停止

time and space complexity

loop through the whole linked list
the time complexity is O(n)
the space complexity is O(1)

coding

class Solution {
    public ListNode swapPairs(ListNode head) {
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode cur = dummy;

        while (cur.next != null && cur.next.next != null) {
            ListNode node2 = cur.next;
            ListNode node3 = cur.next.next;
            ListNode node4 = cur.next.next.next;

            cur.next = node3;
            node3.next = node2;
            node2.next = node4;

            cur = cur.next.next;
        }

        return dummy.next;
    }
}

删除链表的倒数第N个节点

delete the nth to the last node from linked list
Given the head of a linked list, remove the nth node from the end of the list and return its head.

link

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

思路 solution

这道题已经做了多次了
easy

create dummy node before head

use two pointer
one fast, one slow
for (int i = 0; i < k; i++)
move fast

and then move fast and slow both
untill fast move to the end

delete node in slow position

however, when you need to delete nth node
you need to find the n-1 th node and delete n node

therefore fast start from head
slow start from dummy

coding

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode fast = head, slow = dummy;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;

        return dummy.next;
    }
}

intersection of linkedlist 链表交叉

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

link

https://leetcode.com/problems/intersection-of-two-linked-lists/description/

solution 思路

easy 做过多次
use two pointer to iterate through these two linkedlist from the begaining
p1 start from the head of link1
p2 start from the head of link2
once p1 move the end of link1, it should start from the link2
same to p2

once p1 == p2, stop the while loop and return

time and space complexity

O(N + M)
n is len of list1
m is len of list2

coding

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;

        while (p1 != p2) {
            
            if (p1 != null) {
                p1 = p1.next;
            } else {
                p1 = headB;
            }

            if (p2 != null) {
                p2 = p2.next;
            } else {
                p2 = headA;
            }
        }

        return p1;
    }
}

另外一种常规思路
先统计出 长短
计算其中差值 k

然后让指向 长的链表的指针 先移动k步

然后再同时移动 两个指针

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        int len1 = 0, len2 = 0;

        while (p1 != null) {
            p1 = p1.next;
            len1++;
        }

        while (p2 != null) {
            p2 = p2.next;
            len2++;
        }

        int gap = 0;
        p1 = headA;
        p2 = headB;

        if (len1 > len2) {
            gap = len1 - len2;

            while (gap != 0) {
                gap--;
                p1 = p1.next;
            }

        } else {
            gap = len2 - len1;

            while (gap != 0) {
                gap--;
                p2 = p2.next;
            }
        }


        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p1;

    }
}

环形链表 Circular linked list

思路 solution

这道题做错了
I made a mistake in this question
错点在于 如何判断 存在环
The mistake lies in how to determine the existence of a ring
use while loop
the condiition is fast != null and fast.next != null
中间
当 slow == fast 的时候， break
然后判断

fast == null or fast.enxt == null
如果为null 则说明 没环直接返回

coding

public class Solution {
    public ListNode detectCycle(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }

        if (fast == null || fast.next == null) return null;

        // Entrance to the ring

        ListNode p1 = fast;
        ListNode p2 = head;

        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p1;
    }
}