# 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;
    }
```


---

# 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://protegejj.gitbook.io/my-algorithm-summary/data-structure/linked-list.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.