翻转链表

翻转链表

描述
翻转一个链表

样例
给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null

思路

1、 我们需要定义两个临时ListNode,一个保存当前节点下一个节点的地址(nextNode)，一个保存当前节点上一个节点的地址(preNode)

2、 在一次循环中，我们需要保存当前节点的下一个节点的地址(nextNode)

2.1、我们需要更新当前节点的next指向，即指向我们保存的当前节点上一个节点的地址(preNode)

2.2、我们把保存的上一个节点的地址更新为当前节点；即它前面的节点都已经翻转完毕

2.3、我们更新当前节点为下一个节点的地址，我们在前面保存了

3、当我们遍历完所有节点时，我们只需要把我们的上一个节点的地址返回即可

好了，我们跟着思路实现一下

翻转函数

/**
     * 思路：
     *  1、我们需要定义两个临时ListNode,一个保存当前节点下一个节点的地址，一个保存当前节点上一个节点的地址
     *  2、在一次循环中，我们需要保存当前节点的下一个节点的地址
     *  2.1、我们需要更新当前节点的next指向，即指向我们保存的当前节点上一个节点的地址
     *  2.2、我们把保存的上一个节点的地址更新为当前节点；即它前面的节点都已经翻转完毕
     *  2.3、我们更新当前节点为下一个节点的地址，我们在前面保存了
     *  3、当我们遍历完所有节点时，我们只需要把我们的上一个节点的地址返回即可
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head) {
        
        if(head == null || head.next == null) {
            //链表为空或者只有一个节点的直接返回
            return head;
        }
        
        ListNode preNode , nextNode;
        preNode = nextNode = null;
        
        while(head != null) {
            nextNode = head.next;//保存当前节点的下一个节点
            head.next = preNode;//翻转当前节点的指向
            preNode = head;//更新上一个节点
            head = nextNode;//更新当前节点
        }
        
        return preNode;
    }

ListNode类

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
    
    public static void showListNode(ListNode listNode) {
        while(true) {
            if(listNode.next == null ) {
                System.out.print(listNode.val);
                break;
            }else {
                System.out.print(listNode.val+"-->");
            }
            
            listNode = listNode.next;
        }
        
    }
}

测试函数

public static void main(String[] args) {
        ListNode listNode = new ListNode(0);
        for(int i = 1 ; i < 10 ; i++) {
            ListNode temp = new ListNode(i);
            temp.next = listNode;
            listNode = temp;
        }
        
        ListNode.showListNode(listNode);
        
        System.out.println();
        
        listNode = reverse(listNode);
        
        ListNode.showListNode(listNode);
    }