import java.util.LinkedList;
import java.util.List;
/**
* SingleLinkedList
*
* @author atsjp
*/
public class SingleLinkedList<K> {
private Node head = null;
class Node {
private Node next;
private K k;
public Node(K k) {
this.k = k;
}
}
public void addNode(K k) {
if (head == null) {
head = new Node(k);
return;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node(k);
}
public void deleteNode(K k) {
if (head == null) {
return;
}
if (k.equals(head.k)) {
head = head.next;
return;
}
Node prevNode = head, currentNode = head.next;
while (currentNode != null) {
if (k.equals(currentNode.k)) {
if (currentNode.next == null) {
prevNode.next = null;
} else {
prevNode.next = currentNode.next;
}
break;
}
prevNode = currentNode;
currentNode = currentNode.next;
}
}
public void deleteNodeAll(K k) {
if (head == null) {
return;
}
if (k.equals(head.k)) {
head = head.next;
return;
}
Node prevNode = head, currentNode = head.next;
while (currentNode != null) {
if (k.equals(currentNode.k)) {
if (currentNode.next == null) {
prevNode.next = null;
} else {
prevNode.next = currentNode.next;
currentNode = currentNode.next;
continue;
}
}
prevNode = currentNode;
currentNode = currentNode.next;
}
}
public boolean delete(int index) {
if (index < 0 || index > length()) {
return false;
}
if (index == 0) {
head = head.next;
return true;
}
int i = 0;
Node preNode = null;
Node curNode = head;
while (curNode != null) {
if (i == index) {
preNode.next = curNode.next;
return true;
}
preNode = curNode;
curNode = curNode.next;
i++;
}
return false;
}
public int length() {
int i = 0;
Node temp = head;
while (temp != null) {
temp = temp.next;
++i;
}
return i;
}
public void reversal() {
// 用于指向反转链表
Node pReversedHead = head;
// 用于指向当前处理的节点
Node pNode = head;
// 用于暂存已经处理过的上一节点
Node pPrev = null;
while (pNode != null) {
// 暂存next
Node pNext = pNode.next;
// next为空，即表示到达了链表最后一个节点
if (pNext == null) {
// pNode即是反转链表的首节点
pReversedHead = pNode;
}
// 将上一个节点 赋值给 反转链表的下一个节点
pNode.next = pPrev;
// 将当前指向节点 赋值给 上一个节点
pPrev = pNode;
// 将下一个节点 赋值给 当前指向节点
pNode = pNext;
}
this.head = pReversedHead;
}
public List<K> findMiddle1() {
if (head == null) {
return null;
}
List<K> kList = new LinkedList<>();
if (head.next == null) {
kList.add(head.k);
return kList;
}
Node preNode = head, slow = head, fast = head;
while (fast != null && fast.next != null) {
preNode = slow;
slow = slow.next;
fast = fast.next.next;
}
if (fast == null) {
kList.add(preNode.k);
}
kList.add(slow.k);
return kList;
}
public List<K> findMiddle2() {
if (head == null) {
return null;
}
if (head.next == null) {
List<K> kList = new LinkedList<>();
kList.add(head.k);
return kList;
}
Node slow = head, fast = head.next.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
List<K> kList = new LinkedList<>();
if (fast == null) {
kList.add(slow.k);
}
kList.add(slow.next.k);
return kList;
}
public boolean hasLoop() {
Node fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow.equals(fast)) {
return true;
}
}
return false;
}
public String toString() {
StringBuilder temp = new StringBuilder();
temp.append("[");
Node tmp = head;
while (tmp != null) {
temp.append(tmp.k).append(",");
tmp = tmp.next;
}
if (temp.length() >= 3) {
temp.deleteCharAt(temp.length() - 1);
}
temp.append("]");
return temp.toString();
}
}
