Linked List

Nodes.
Each node has a value and a link to next node. (singly)

基本操作：
1. Create a Linked List

class Node {
 Node next = null;
 int data;
 public Node(int d) {
  data = d;
 }
 
 void appendToTail(int d) {
  Node end = new Node(d);
  Node n = this;
  while (n.next != null) { n = n.next; }
  n.next = end;
 }
}

2. Deleting a Node from Singly Linked List
    1) Delete a node, given head node and the value of the node to be deleted. (singly)
   

Node deleteNode(Node head, int d) {
  Node n = head;
  if (n.data == d) {
   return head.next;
  }
  while (n.next != null) {
   if (n.next.data == d) {
    n.next = n.next.next;
    return head; //head not change
   }
   n = n.next;
  }
  return head; //return head if d is not in the list
 }

    2) Delete a node from the middle, only access to that node. (Leetcode)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        if (node == null || node.next == null) return;
        node.val = node.next.val;
        node.next = node.next.next;
        node = node.next;
    }
}

3. Reverse a singly linked list
    1) Recursive

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode second = head.next;
        head.next = null;
        ListNode node = reverseList(second);
        second.next = head;
        return node;
    }
}

    2) Iterative

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
}

实际应用: