一、反转单向链表

private static void reverseNode(Node head) {
    Node pre = null;
    Node currentNode = head;

    while (currentNode != null) {
        Node next = currentNode.next;
        currentNode.next = pre;
        pre = currentNode;
        currentNode = next;
    }

二、反转双向链表

private static void reverseNode(Node head) {
        Node currentNode = head;
        Node temp = null;
        while (currentNode != null) {
            temp = currentNode.next;
            currentNode.next = currentNode.pre;
            currentNode.pre = temp;
            currentNode = temp;

        }
    }

三、判断一个链表是否为回文结构

[题目]给定一个单链表的头节点head，请判断该链表是否为回文结返回true;

[例子] 1->2->1，返回true;

1->2->2->1，返回true;

15->6->15，返回true;

1->2->3，返回false。

[要求]如果链表长度为N，时间复杂度达到0(N)，额外空间复杂度大到0(1)

3.1 使用 Stack来解决（空间复杂度 N）

/**
 * 使用栈来解决，空间复杂度是 N
 */
private static boolean checkhuiwen(Node head) {
    if (head == null) {
        return false;
    }
    Stack<Node> stack = new Stack<>();
    Node p1 = head;
    while (p1 != null) {
        stack.push(p1);
        p1 = p1.next;
    }

    Node p2 = head;
    while (!stack.isEmpty()) {
        if (stack.pop().value != p2.value) {
            return false;
        }
        p2 = p2.next;
    }
    return true;

}

3.2 使用快慢指针来解决（空间复杂度 1）

切成两边，然后从中间往两边进行比对，比对后，再给反转回来就行了~

/**
 * 使用指针来解决，空间复杂度是 1
 */
private static boolean checkhuiwen2(Node head) {
    if (head == null || head.next == null) {
        return true; // 空链表或者只有一个节点时，认为是回文结构
    }

    Node fastP = head;
    Node slowP = head;

    while (fastP.next != null && fastP.next.next != null) {
        slowP = slowP.next;
        fastP = fastP.next.next;
    }

    Node p1 = head;
    Node pre = null;
    Node next = null;
    while (true) {
        next = p1.next;
        p1.next = pre;
        if(p1 == slowP){
            break;
        }
        pre = p1;
        p1 = next;
    }

    Node pleft = slowP; // 前半部分反转后的头节点
    Node pRight = next;

    if(fastP.next == null){ // 链表长度奇数个
        pleft = pleft.next;
    }

    boolean flag = true;
    while (pleft != null && pRight != null) {
        if(pleft.value != pRight.value){
            flag = false;
            break;
        }
        pleft = pleft.next;
        pRight = pRight.next;
    }

    // 数组恢复原状
    head = reverseLink(slowP);
    slowP.next = next;

    return flag;
}

// <-1  2 -> 3 -> 4
public static Node reverseLink(Node head){
    Node pre = null;
    Node next = null;
    Node p1 = head;
    while(p1 != null){
        next = p1.next;
        p1.next = pre;
        pre = p1;
        p1 = next;
    }

    return pre; // 返回新的头结点
}

四、将单向链表切分左中右

将单向链表按某值划分成左边小、中间相等、右边大的形式

（其实跟快速排序有点像，但是快排的空间复杂度是 NlogN，时间复杂度是 NlogN，并且快排是不稳定的）

[题目] 给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。

实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。

[要求]稳定性

[要求] 时间复杂度请达到0(N)，额外空间复杂度请达到0(1)。

public static class Node {
    private int value;
    private int index;
    private Node next;

}

public static void main(String[] args) {
    Node aNode = new Node();
    aNode.index = 0;
    aNode.value = 1;

    Node bNode = new Node();
    bNode.index = 1;
    bNode.value = 3;

    Node cNode = new Node();
    cNode.index = 2;
    cNode.value = 1;

    Node dNode = new Node();
    dNode.index = 3;
    dNode.value = 5;

    Node eNode = new Node();
    eNode.index = 4;
    eNode.value = 2;

    Node fNode = new Node();
    fNode.index = 5;
    fNode.value = 10;

    Node gNode = new Node();
    gNode.index = 6;
    gNode.value = 2;

    Node hNode = new Node();
    hNode.index = 7;
    hNode.value = 3;

    aNode.next = bNode;
    bNode.next = cNode;
    cNode.next = dNode;
    dNode.next = eNode;
    eNode.next = fNode;
    fNode.next = gNode;
    gNode.next = hNode;
    splitPartition(aNode ,3);
}

private static void splitPartition(Node head,int target) {
    Node smallHead = null;
    Node smallEnd = null;

    Node equalsHead = null;
    Node equalsEnd = null;

    Node biggerHead = null;
    Node biggerEnd = null;

    Node p = head;
    while(p != null){
        if(p.value < target){
            if(null != smallEnd){
                smallEnd.next = p;
            }
            smallEnd = p;

            if(null == smallHead){
                smallHead = p;
            }
        }
        else if(p.value == target){
            if(null != equalsEnd){
                equalsEnd.next = p;
            }
            equalsEnd = p;
            if(null == equalsHead){
                equalsHead = p;
            }
        } else {
            if(null != biggerEnd){
                biggerEnd.next = p;
            }
            biggerEnd = p;
            if(null == biggerHead){
                biggerHead = p;
            }
        }
        p = p.next;
    }

    // 极端情况下， target 都比链表中的值小，那么 biggerHead 和 biggerEnd 都会指向 null
    if(null != biggerEnd){
        biggerEnd.next = null;
    }
    // 极端情况下， target 都比链表中的值大，那么 smallHead 和 smallEnd 都会指向 null
    if(null != smallEnd){
        smallEnd.next = equalsHead;
    }
    // 极端情况下， target 跟链表中对比，没有相等的，那么 equalsHead 和 equalsEnd 都会指向 null
    if(null != equalsEnd){
        equalsEnd.next = biggerHead;
    }
}