> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/linked_list/singly-linked-list/plus-one-linked-list.md).

# Plus One Linked List

## Question ([LC.369](https://leetcode.com/problems/plus-one-linked-list/))

> Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list.

## Analysis

The head node might get modified. Dummy head is needed.

## Code

```java
public ListNode plusOne(ListNode head) {
    // increment j if less than 9
    // increment i if equal to 9, and zero the rest
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    ListNode leastSig = dummyNode; // if less than 9
    ListNode mostSig = dummyNode; // if carry is necessary
    // locate leastSig and mostSig
    while (leastSig.next != null) {
        leastSig = leastSig.next;
        if (leastSig.val < 9) mostSig = leastSig;
    }
    // decide which one to increment
    if (leastSig.val < 9) {
        leastSig.val ++;
    } else {
        mostSig.val++;

        mostSig = mostSig.next;
        while (mostSig != null) {
            mostSig.val = 0;
            mostSig = mostSig.next;
        }
    }
    // decide which one to return
    if (dummyNode.val == 1)
        return dummyNode;
    return head;
}
```