> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/my-algorithm-summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/my-algorithm-summary/data-structure/linked-list.md).

# Linked List

## Linked List

## 1. Delete a node

(1) If we can access the node directly, we can override its value with the value of its next node. **This won't work if the node to be deleted is at the tail of the list**

```java
    public void deleteNodeWithDirectAccess(ListNode node) {
        if (node == null || node.next == null) {
            return;
        }

        node.val = node.next.val;
        node.next = node.next.next;
    }
```

(2) If we cannot access the node directly, we have to iterate over the list and find the node and keep track of its previous node

```java
    public void deleteNodeWithoutDirectAccess(ListNode head, ListNode node) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode preNode = dummy, curNode = head;
        while (curNode != null) {
            if (curNode == node) {
                preNode.next = curNode.next;
                return;
            }
            preNode = preNode.next;
            curNode = curNode.next;
        }
        return dummy.next;
    }
```

## **2. Reverse the list**

（1）Reverse the whole list

```java
    public ListNode reverseList(ListNode node) {
        ListNode preNode = null, nextNode = null;
        ListNode curNode = node;

        while (curNode != null) {
            nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }
```

（2）Reverse part of the list ([Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/?tab=Description))

```java
   // start and end are used as sentinels here, we are going to reverse the part between start node
   // and end node
   public ListNode reverse(ListNode start, ListNode end) {
        ListNode last = start.next;
        ListNode curNode = last.next;

        while (curNode != end) {
            last.next = curNode.next;
            curNode.next = start.next;
            start.next = curNode;
            curNode = last.next;
        }
        return last;
    }
```

## 3. Split a list into two halves

Use two pointers (fast and slow) to split a list into halves

```java
    public void splitList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        ListNode fast = head, slow = head;

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

        // Get the head of the second half
        ListNode secondHalf = slow.next;
        // Cut the list
        slow.next = null;
    }
```