Leetcode Day 4 - Advanced Linked List Operations

Linked List 2¹

Diff	Problem	Python	C++
	24 Swap Nodes in Pairs	✅	✅
	19 Remove Nth Node From End of List	✅
	160 Intersection of Two Linked Lists	✅
	142 Linked List Cycle II	✅

Swap Nodes in Pairs

Link to Leetcode question²

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.)

Example 1

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2

Input: head = []
Output: []

Example 3

Input: head = [1]
Output: [1]

Solution³

Python

class Solution(object):
    def swapPairs(self, head):
        if head is None or head.next is None:
            return head

        odd = head
        even = head.next
        old = None

        while((even is not None) and (odd is not None)):
            odd.next = even.next
            even.next = odd
            if old is not None:
                old.next = even
            else:
                head = even
            old = odd
            odd = odd.next
            
            if odd is not None:
                even = odd.next
        
        return head

C++

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0);  
        dummy.next = head;
        ListNode* prev = &dummy;

        while (prev->next && prev->next->next) {
            ListNode* first = prev->next;
            ListNode* second = first->next;

            first->next = second->next;
            second->next = first;
            prev->next = second;

            prev = first;
        }

        return dummy.next;
    }
};

Similar Questions

Diff	Similar Questions	Python	Java
	1721 Swapping Nodes in a Linked List4
	25 Reverse Nodes in k-Group5

Remove Nth Node From End of List

Link to Leetcode question⁶

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

Example 1

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2

Input: head = [1], n = 1
Output: []

Example 3

Input: head = [1,2], n = 1
Output: [1]

Solution⁷

Python

class Solution(object):
    def removeNthFromEnd(self, head, n):
        cur = head
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        nth = cur
        i = 1

        while cur.next is not None:
            if i == n:
                prev = nth
                nth = nth.next
            else:
                i += 1
            cur = cur.next
        
        prev.next = nth.next

        return dummy.next

Similar Questions

Diff	Similar Questions	Python	Java
	2095 Delete the Middle Node of a Linked List8

Intersection of Two Linked Lists

Link to Leetcode question⁹

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:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'

Example 2

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection

Solution¹⁰

Python

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        pA = headA
        pB = headB
        noneA = True
        noneB = True

        while(pA != pB):
            if(pA.next is not None):
                pA = pA.next
            elif(noneA):
                pA = headB
                noneA = False
            else:
                return None
            
            if(pB.next is not None):
                pB = pB.next
            elif(noneB):
                pB = headA
                noneB = False
            else:
                return None
        return pA

Similar Questions

Diff	Similar Questions	Python	Java
	599 Minimum Index Sum of Two Lists11

Linked List Cycle II

Link to Leetcode question¹²

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Solution¹³

Python

class Solution(object):
    def detectCycle(self, head):
        if head is None:
            return None

        fast, slow = head, head

        while(fast is not None and fast.next is not None):
            fast = fast.next.next
            slow = slow.next
            if(fast == slow):
                break
        
        if(fast is None or fast.next is None):
            return None

        fast = head
        while(fast != slow):
            fast = fast.next
            slow = slow.next
        
        return fast

Similar Questions

Diff	Similar Questions	Python	Java
	287 Find the Duplicate Number14

Reference

1. 代码随想录-链表理论基础: https://programmercarl.com/链表理论基础.html ↩︎

2. Leetcode-24 Swap Nodes in Pairs: https://leetcode.com/problems/swap-nodes-in-pairs/description/ ↩︎

3. 代码随想录-两两交换链表中的节点: https://programmercarl.com/0024.两两交换链表中的节点.html. ↩︎

4. Leetcode-1721 Swapping Nodes in a Linked List: https://leetcode.com/problems/swapping-nodes-in-a-linked-list/description/. ↩︎

5. Leetcode-25 Reverse Nodes in k-Group: https://leetcode.com/problems/reverse-nodes-in-k-group/. ↩︎

6. Leetcode-19 Remove Nth Node From End of List: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/. ↩︎

7. 代码随想录-删除链表的倒数第N个节点: https://programmercarl.com/0019.删除链表的倒数第N个节点.html. ↩︎

8. Leetcode-2095 Delete the Middle Node of a Linked List: https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/. ↩︎

9. Leetcode-160 Intersection of Two Linked Lists: https://leetcode.com/problems/intersection-of-two-linked-lists/description/. ↩︎

10. 代码随想录-面试题 02.07. 链表相交: https://programmercarl.com/面试题02.07.链表相交.html. ↩︎

11. Leetcode-599 Minimum Index Sum of Two Lists: https://leetcode.com/problems/minimum-index-sum-of-two-lists/. ↩︎

12. Leetcode-142 Linked List Cycle II: https://leetcode.com/problems/linked-list-cycle-ii/description/. ↩︎

13. 代码随想录-环形链表II:https://programmercarl.com/0142.环形链表II.html. ↩︎

14. Leetcode-287 Find the Duplicate Number: https://leetcode.com/problems/find-the-duplicate-number/. ↩︎