# 1 LinkedList

* **Design**

> <https://leetcode.com/problems/design-linked-list/description/>

* **Reverse**

```java
public ListNode reverseList(ListNode head) {
    /* iterative solution */
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

public ListNode reverseList(ListNode head) {
    /* recursive solution */
    return reverseListInt(head, null);
}

private ListNode reverseListInt(ListNode prev, ListNode head) {
    if (head == null)
        return prev;
    ListNode next = head.next;
    head.next = prev;
    return reverseListInt(head, next);
}
```

\*Reverse for an interval \[m, n]

![](/files/-LSLuabQGfrRJc9lia_S)

```java
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode sentinel = new ListNode(-99);
        sentinel.next = head;
        ListNode pre = sentinel;
        ListNode cur = sentinel.next;
        for (int i = 1; i < m; i++) {
            cur = cur.next;
            pre = pre.next;
        }
        for (int i = 0; i < n - m; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return sentinel.next;
    }
}
```

* **Insert**

```java
public ListNode insertNode(ListNode head, int val) {
    // write your code here
    ListNode node = new ListNode(val);
    if (head == null) return node;

    ListNode dummy = new ListNode(-99);
    dummy.next = head;
    head = dummy;

    while (head.next != null && head.next.val < val) {
        head = head.next;
    }

    node.next = head.next;
    head.next = node;

    return dummy.next;
}
```

* **Delete**

Remove Nth Node From End of List

```java
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;

        ListNode slow = sentinel;
        ListNode fast = sentinel;

        // the diff of fast and slow is n
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

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

        slow.next = slow.next.next;

        return sentinel.next;
    }
}
```

Remove Linked List Elements

(注意下没准要删除的元素是连续的，那种情况下不要动 head)

```java
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        ListNode sentinel = new ListNode(-99);
        sentinel.next = head;
        ListNode cur = sentinel; //prev
        while (cur.next != null) {
            if (cur.next.val == val) {
                head = head.next;
                cur.next = head;
            } else {
                cur = cur.next;
                head = head.next;
            }
        }

        return sentinel.next;
    }
}
```

Delete Node in a Linked List

(Shift the elements after the deleted one)

```java
class Solution {
    public void deleteNode(ListNode node) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = node;
        while (node.next != null) {
            sentinel.next.val = node.next.val;
            sentinel = node;
            node = node.next;
        }

        sentinel.next = null;
    }
}
```

Remove Duplicates from Sorted List

```java
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        while (head != null && head.next != null) {
            if (head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }

        return dummy.next;
    }
}
```

* **Swap**

Swap Nodes in Pairs

```java
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode sentinel = new ListNode(-99);
        sentinel.next = head;

        ListNode l1 = sentinel;
        ListNode l2 = head;
        while (l2 != null && l2.next != null) {
            ListNode nextStart = l2.next.next;

            l1.next = l2.next;
            l2.next.next = l2;
            l2.next = nextStart;

            l1 = l2;
            l2 = l1.next;
        }
        return sentinel.next;
    }
}
```

Odd Even Linked List (odd place ones first, then even ones)

```java
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode odd= head, even = head.next;
        ListNode evenHead = even; // record even's head
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}
```

* **Merge (Sorted)**

```java
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;

        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                head.next = l1;
                l1 = l1.next;
            } else {
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
        }
        while(l1 != null){
            head.next = l1;
            l1 = l1.next;
            head = head.next;
        }
        while(l2 != null){
            head.next = l2;
            l2 = l2.next;
            head = head.next;
        }

        return dummy.next;
    }
}
```

```java
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}
```

* **Middle**

```java
public ListNode findMiddle(ListNode head) { // second one
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;        
}
```

```java
public ListNode findMiddle(ListNode head) { // first one
    if (head == null || head.next == null) {
        return head;
    }

    ListNode fast = head.next, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}
```

* **Reverse Print**

```java
private static void reversePrintList_recursive(ListNode head){
    if(head.next == null){
        System.out.print(head.val + ",");
        return;
    }
    reversePrintList_recursive(head.next);
    System.out.print(head.val + ",");
}

private static void reversePrintList_iterative(ListNode head){
    int size = 0;
    ListNode cur = head;
    while(cur != null){
        size++;
        cur = cur.next;
    }

    for(; size > 0; size --){
        ListNode ptr = head;
        for(int i = 0; i < size - 1; i++) ptr = ptr.next;
        System.out.print(ptr.val + ",");
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://luj.gitbook.io/code/data-structure/linkedlist.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.