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

    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

    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

    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)

   // 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

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