剑指Offer (十五):反转链表(Java版)

对于一个单向链表来说，上一条数据只能指向下一条数据（如下图），那我们想反转这个链表，变成下图这个样子，怎么实现呢？

1->2->3->4->5      5->4->3->2->1

首先第一种方式，直接反转顺序，将2->1 ,3->2 以此类推，则完成了链表的反转，具体实现为，定义三个指针，pre,cur,next每次遍历链表的时候，cur指向pre,然后再将cur赋值给pre,next赋值给cur，具体代码如下

private static ListNode firstReverse(ListNode listNode){
    if(null == listNode || null == listNode.next){
        return listNode;
    }
    ListNode listNodePre = null;
    ListNode listNodeCur = listNode;
    ListNode listNodeNext = null;
    while (null != listNodeCur){
        listNodeNext = listNodeCur.next;
        listNodeCur.next = listNodePre;
        listNodePre = listNodeCur;
        listNodeCur = listNodeNext;
    }
    return listNodePre;
}

第二种方式，利用栈的特性，先进后出，循环遍历链表进栈，然后依次出栈，组成一个新的链表即可，具体代码如下

private static ListNode secondReverse(ListNode head){
    if(null == head || null == head.next){
        return head;
    }
    ListNode listNodeReverse = null;
    ListNode listNodeFirst = null;
    Stack<ListNode> listNodeStack = new Stack<>();
    while (null != head){
        listNodeStack.push(head);
        head = head.next;
    }
    if(!listNodeStack.isEmpty()){
        listNodeFirst = listNodeStack.pop();
    }
    listNodeReverse = listNodeFirst;
    while (!listNodeStack.isEmpty()){
        listNodeReverse.next = listNodeStack.pop();
        listNodeReverse = listNodeReverse.next;
    }
    listNodeReverse.next = null;
    return listNodeFirst;
}

第三种，则可以采用递归的方式来解决，如果当前节点为空或者当前节点的下一个节点为空，则返回该节点，不然就将该节点的下一个节点指向当前节点，代码如下

private static ListNode thridReverse(ListNode head){
    if(null == head || null == head.next){
        return head;
    }
    ListNode listNodeFirst = head.next;//2
    head.next = null;
    ListNode listNode = thridReverse(listNodeFirst);
    listNodeFirst.next=head;
    return listNode;
}

完整代码如下

public class MainReverseListNode {

    public static void main(String[] args) {

        ListNode listNode0 = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        listNode0.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        //ListNode reverse = firstReverse(listNode0);
        ListNode secondReverse = thridReverse(listNode0);
        System.out.print(secondReverse.toString());

    }


    private static ListNode firstReverse(ListNode head){
        if(null == head || null == head.next){
            return head;
        }
        ListNode listNodePre = null;
        ListNode listNodeCur = head;
        ListNode listNodeNext = null;
        while (null != listNodeCur){
            listNodeNext = listNodeCur.next;
            listNodeCur.next = listNodePre;
            listNodePre = listNodeCur;
            listNodeCur = listNodeNext;
        }
        return listNodePre;
    }


    private static ListNode secondReverse(ListNode head){
        if(null == head || null == head.next){
            return head;
        }
        ListNode listNodeReverse = null;
        ListNode listNodeFirst = null;
        Stack<ListNode> listNodeStack = new Stack<>();
        while (null != head){
            listNodeStack.push(head);
            head = head.next;
        }
        if(!listNodeStack.isEmpty()){
            listNodeFirst = listNodeStack.pop();
        }
        listNodeReverse = listNodeFirst;
        while (!listNodeStack.isEmpty()){
            listNodeReverse.next = listNodeStack.pop();
            listNodeReverse = listNodeReverse.next;
        }
        listNodeReverse.next = null;
        return listNodeFirst;
    }

    private static ListNode thridReverse(ListNode head){
        if(null == head || null == head.next){
            return head;
        }
        ListNode listNodeFirst = head.next;//2
        head.next = null;
        ListNode listNode = thridReverse(listNodeFirst);
        listNodeFirst.next=head;
        return listNode;
    }

}