Post

Leetcode Day 4 - Advanced Linked List Operations

Focuses on more complex linked list problems, such as swapping nodes in pairs, removing nodes from specific positions, detecting intersections between two lists, and identifying cycles within a linked list, requiring advanced pointer manipulation and boundary case handling.

Posted Updated
By Le Lyu
views 6 min read

Linked List 21

DiffProblemPythonJava
Medium24 Swap Nodes in Pairs✅ 
Medium19 Remove Nth Node From End of List✅ 
Easy160 Intersection of Two Linked Lists✅ 
Medium142 Linked List Cycle II✅ 

Swap Nodes in Pairs

Link to Leetcode question2

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

Desktop View

1
2

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

Example 2

1
2

Input: head = []
Output: []

Example 3

1
2

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

Solution3

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

Similar Questions

DiffSimilar QuestionsPythonJava
Medium1721 Swapping Nodes in a Linked List4  
Hard25 Reverse Nodes in k-Group5  

Remove Nth Node From End of List

Link to Leetcode question6

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

Example 1

Desktop View

1
2

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

Example 2

1
2

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

Example 3

1
2

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

Solution7

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

DiffSimilar QuestionsPythonJava
Medium2095 Delete the Middle Node of a Linked List8  

Intersection of Two Linked Lists

Link to Leetcode question9

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:

Desktop View

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:

Desktop View

1
2

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

Desktop View

1
2

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

Solution10

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

DiffSimilar QuestionsPythonJava
Easy599 Minimum Index Sum of Two Lists11  

Linked List Cycle II

Link to Leetcode question12

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

Desktop View

1
2
3

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

Desktop View

1
2
3

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

Desktop View

1
2
3

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

Solution13

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

DiffSimilar QuestionsPythonJava
Easy287 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/. ↩︎

Data Structure and Algorithm, Leetcode, Linked List
linked list recursion double pointers hash table
This post is licensed under CC BY 4.0 by the author.