LeetCode 369: Plus One Linked List Solution

Master LeetCode problem 369 (Plus One Linked List), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

369. Plus One Linked List

Medium

Linked List Math

Problem Explanation

Explanation:

To solve this problem, we can reverse the linked list, add one to the first node (head), and propagate the carry if needed. Then, we reverse the linked list back to its original order.

Here is the step-by-step algorithm:

Reverse the linked list.
Add one to the value of the first node. If the sum is less than 10, update the value and return the reversed linked list.
If the sum is 10, set the value of the current node to 0 and move to the next node, propagating the carry.
After reaching the end of the linked list, if there is still a carry, add a new node with value 1.
Reverse the linked list back to its original order.

Time complexity: O(n) where n is the number of nodes in the linked list. Space complexity: O(1)

Solution Code

class Solution {
    public ListNode plusOne(ListNode head) {
        if (head == null) {
            return null;
        }

        head = reverseLinkedList(head);

        ListNode current = head;
        int carry = 1;

        while (current != null) {
            int sum = current.val + carry;
            if (sum < 10) {
                current.val = sum;
                return reverseLinkedList(head);
            } else {
                current.val = 0;
                if (current.next == null) {
                    current.next = new ListNode(1);
                    return reverseLinkedList(head);
                }
                current = current.next;
            }
        }

        return reverseLinkedList(head);
    }

    private ListNode reverseLinkedList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        ListNode next = null;

        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        return prev;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 369 (Plus One Linked List)?

This page provides optimized solutions for LeetCode problem 369 (Plus One Linked List) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 369 (Plus One Linked List)?

The time complexity for LeetCode 369 (Plus One Linked List) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 369 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 369 in Java, C++, or Python.

Back to LeetCode Solutions