Data Structure | Singly LinkedList

Singly Linked List 即单向链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

对于一个单向链表来说，我们需要考虑如下的操作：

如何在Java中构建一个单向链表

首先需要构造一个 LinkedList class，它包含 Node class
对于每一个 Node 来说，它需要储存 data 和下一个 node 的 reference，这可以用构造器来完成

class LinkedList{      
   static Node head;    // head of list         
   
   static class Node{    // Linked List Node, the inner class is made static
   	int data;         // so that main() can access it
   	Node next;
   	Node(int data){    // constructor
   	    this.data = data;
   	    next = null;
   	}
   } 
}

如何打印出整个链表中的元素

遍历(Iterative)整个链表

public void printList(){  
    Node temp = head;
    while (temp != null){
	System.out.print(temp.data + " ");
	temp = temp.next;
    }
    System.out.println();
}

如何向链表中添加元素

向链表中添加元素分为三种情况:

在链表头添加

// Add a node at the front
public void push(int newData){   // O(1)
    Node newNode = new Node(newData);  // Allocate the Node & Put in the data
    newNode.next = head;   // Make next of new Node as head
    head = newNode;     // Move the head to point to new Node
}

在链表中某个指定的位置添加

// Add a node after a given node
public void insertAfter(Node preNode, int newData){   // O(1)
    if (preNode == null){
        System.out.println("The given previous node cannot be true");
        return;
    }
    Node newNode = new Node(newData);  // Allocate the Node & Put in the data
    newNode.next = preNode.next;   // Make next of newNode as next of preNode
    preNode.next = newNode;   // Make next of preNode as newNode   
}

在链表尾添加

// Add a node at the end
public void append(int newData){   // O(n)
    Node newNode = new Node(newData);
    //If the Linked List is empty, then make the new node as head
    if (head == null){
        head = new Node(newData);
        return;
    }
    // This new node is gonna be last node, so make next of it as null
    newNode.next = null;  
    Node last = head;
    while (last.next != null){   // Traverse till the last node
        last = last.next;
    }
    last.next = newNode;      // Change the next of last node
}

如何删除链表中的节点

删除链表中的节点又分为以下两种情况：

给定元素的值，删除该值第一次出现在链表中的那个节点

// Given a key, delete the first occurence of the key in Linked List
public void deleteKey(int key){
    Node temp = head, prev = null;
    // If head itself holds the key to be deleted
    if (temp != null && temp.data == key){
	head = temp.next;
	return;
    }
    // earch for the key to be deleted
    while (temp != null && temp.data != key){
	prev = temp;
	temp = temp.next;
    }
    // If key was not presented in the Linked LIst
    if (temp == null) return;
    // Unlink the node from linked list
    prev.next = temp.next;
}

给定节点所在的位置（position），删除该节点

// Given a reference (pointer to pointer) to the head of a list
// and a position, deletes the node at the given position
public void deleteNode(int position){
    if (head == null) return;    // If the linked list is empty
    Node temp = head;    // Store head node
    // If head needs to be removed
    if (position == 0){
	head = temp.next;
	return;
    }
    // Find previous node of the node to be deleted
    for (int i = 0; temp != null && i < position - 1; i++){
	temp = temp.next;
    }
    if (temp == null || temp.next == null) return;
    // Node temp -> next is the node to be deleted,
    // Store pointer to the next of node to be deleted
    Node next = temp.next.next;
    temp.next = next;    // Unlink the deleted node from list
}

如何获取节点数目

有两种方法：Iterative 和 Recursive

Iterative method 获取节点数目

// Count number of nodes in a given singly linked list by iterative
public int getCountIte(){
    Node temp = head;
    int count = 0;
    while (temp != null){
	count++;
	temp = temp.next;
    }
    return count;
}

Recursive method 获取节点数目

// Count number of nodes in a given singly linked list by recursive
public int getCountRec(Node node){
    if (node == null) return 0;
    return 1 + getCountRec(node.next);
}

给定两个数据x和y，如何交换包含数据的两个节点

（需要注意的是，在此处的“交换”指交换node，而非节点中的data）

这个操作略微有些复杂，我们需要考虑如下步骤：
1.如果x和y相等，直接return
2.找到x和y的节点和它们的前一个节点（应为我们需要交换它们，找到前一个节点能为我们提供reference）
3.如果x和y中有一个不存在（或都不存在），直接return
4.如果x为head，把y设为新的head；如果y为head，把x设为新的head
5.交换两个节点的下一个节点（使用temp，就像交换两个variable一样）

// Funciton to swap Nodes x and y in linked list by changing links
public void swapNodes(int x, int y){
    if (x == y) return;   // Nothing to do if x and y are the same
    // Search for x (keep track of prevX and CurrX)
    Node prevX = null, currX = head;
    while (currX != null && currX.data != x){
	prevX = currX;
	currX = currX.next;
    }
    // Search for y (keep track of prevY and CurrY)
    Node prevY = null, currY = head;
    while (currY != null && currY.data != x){
	prevY = currY;
	currY = currY.next;
    }
    // If either x or y is not present, do nothing
    if (currX == null || currY == null) return;  
    if (prevX != null) prevX.next = currY; // If x is not head of linked list
    else head = currY;  // else let y be the new head
    if (prevY != null) prevY.next = currX; // If y is not head of linked list
    else head = currX;  // else let x be the newhead
    // Swap next pointers
    Node temp = currX.next;
    currX.next = currY.next;
    currY.next = temp;
}

如何reverse单向链表

Example:
Input : Head of following linked list: 1->2->3->4->5->NULL
Output : Linked list should be changed to: 5->4->3->2->1->NULL

有两种方法：Iterative 和 Recursive

Iterative method to reverse a linked list

// Reverse a linked list in iterative method
public Node reverseIte(Node node){
    Node prev = null;
    Node curr = node;
    Node next = null;
    while (curr != null){
	next = curr.next;
	curr.next = prev;
	prev = curr;
	curr = next;
    }
    node = prev;
    return node;
}

对于初学者来说，单看代码理解起来可能有些困难
这里有一个很好的 reference 材料，讲的清晰且易懂：
YouTube video on reserve a linked list using Iterative method (需要翻墙)

Recursive method to reverse a linked list

Recursive 地 reverse linked list 需要如下几个步骤：
1）Base Case: 当 “node” 为最后一个节点时，把它设为新的 head
2）递归的调用该函数（此时 node 跳到上一个 stack 中， node 为倒数第二个节点）
3）使 node.next 指向 node， node 本身指向 null

public Node reverseRec(Node node){
    if (node.next == null){
	head = node;          
	return null;
    }
    reverseRec(node.next);
    Node temp = node.next;   // When code reached the base case,
    temp.next = node;        // "node" now refers to the second last node
    node.next = null;
    return head;
}

关于用 recursive method 去 reverse linked list，这里有个不错的学习资料：
Recursive method to reverse a linked list (需要翻墙)

除了以上这些基本方法以外，针对 linked list 还有一些稍微更复杂一点的操作：

给定两个已经排好序（从小到大）的 linked list 比如 a 和 b，如何把它们合并成一个单独的递增的 linked list

Example:
The first linked list a is 5->10->15
The second linked list b is 2->3->20
Then SortedMerge() should return a pointer to the head node of the merged list 2->3->5->10->15->20

public Node sortedMerge(Node a, Node b){
    Node result = null;
    if (a == null) return b; // Base case
    if (b == null) return a;
    // Pick either a or b, and recursivly sort it
    if (a.data <= b.data){
	result = a;
	result.next = sortedMerge(a.next, b);
    }
    else {
	result = b;
	result.next = sortedMerge(b.next, a);
    }
    return result;
}

了解了以上步骤后，在此基础上，我们来看另一个有些复杂的操作：

给定一个无序的 linked list，如何用 merge sort 对其排序

分为三个步骤：

1）找到中间节点 middle

如何在不知道 linked list 长度的情况下找到中间的节点呢？这里提供一种比较巧妙的思路：

创建两个指针，fastPointer 移动两格，slowPointer 移动一格，当 fastPointer 为 null 时，slowPointer 指向中间的 node，Java 代码实现如下：

/* Step 1, we need a getMiddle method */
public Node getMiddle(Node node){
    if (node == null) return node;
    Node fastPointer = node.next;
    Node slowPointer = node;
    while (fastPointer != null){
	fastPointer = fastPointer.next;
	if (fastPointer != null){
	    slowPointer = slowPointer.next;
  	    fastPointer = fastPointer.next;
	}
    }
    return slowPointer;
}

2）此时 linked list 被分为左右两个部分，分别对其递归的使用 mergeSort
3）用我们已经讨论锅的上一个操作 sortedMerge 对左右两个进行合并

// Step 2 and Step 3, mergeSort
public Node mergeSort(Node node){
    if (node == null || node.next == null) return node;   // base case
    // Get the middle of the list
    Node middle = getMiddle(node);  
    Node nextToMiddle = middle.next;
    // This is the end of left linked list, so set to null
    middle.next = null;  
    Node left = mergeSort(node);      // Apply mergeSort on left list
    Node right = mergeSort(nextToMiddle);   // Apply mergeSort on right list
    Node sortedList = sortedMerge(left, right);
    return sortedList;
}

给定一个 Linked List 和 size k, 如何在 k 的范围内 reverse Linked List

Example:
Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3
Output: 3->2->1->6->5->4->8->7->NULL.

Inputs: 1->2->3->4->5->6->7->8->NULL and k = 5
Output: 5->4->3->2->1->8->7->6->NULL.

// Reverse a Linked List in groups of given size
public Node reverseByGroup(Node head, int k){
    Node curr = head;
    Node next = null;
    Node prev = null;
    int count = 0;
    // Reverse first k nodes of linked list
    while (count < k && curr != null){
	next = curr.next;
	curr.next = prev;
	prev = curr;
	curr = next;
	count++;
    }
    // next now is a pointer to (k + 1)th node
    // Recursively call for the list starting from current
    // And make rest of the list as next of first node
    if (next != null){
	head.next = reverseByGroup(next, k);
    }
    return prev;
}