数据结构专题：1.单向链表反转与排序

有如下单向链表

static   class Node {
        int i;
        Node next;
    }

1.单向链表反转，递归

public static Node reverse(Node head){
        if(head==null||head.next==null){
            return head;
        }
        Node newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

递归的方式其实是从尾节点开始进行指针反转，最终递归反转到头节点

2.单向链表反转，非递归

public static Node reverse2(Node head){
        if(head==null||head.next==null){
            return head;
        }
        Node newHead = null;
        while(head!=null){
            Node tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }

非递归采用指针法，从头节点开始，依次反转，重点是又一个tmp，记录head.next，这样反转之后，可以找到之前的next节点。

3.单向链表-快排(递归)

public static void swapValue(Node a,Node b){
        int tmp = a.i;
        a.i = b.i;
        b.i = tmp;
    }

    public static Node partion(Node head,Node end){
        if(head==null||head.next==null){
            return head;
        }
        Node p =head,j = head.next;
        while(j!=end){
            if(j.i<head.i){
                p = p.next;
                swapValue(p,j);
            }
            j = j.next;
        }
        if(p!=head){
            swapValue(p,head);
        }
        return p;
    }

    public static void quickSort(Node head,Node end){
        if(head!=end) {
            Node p = partion(head, end);
            quickSort(head, p);
            quickSort(p.next, end);
        }
    }

leetCode上面148题与此相同，利用的是值交换。