# 链表反转

on3Rln.png

# for 循环 实现

思路:要实现链表反转就需要记录 3 个元素:当前元素(用来 for 循环判断),前一个元素(反转指针指向的目标),后一个元素(用来记住链表的路径)

具体的代码:

ListNode.java

public class ListNode {  
	Object data;
    ListNode next;
    public ListNode (){
        this.data = null;
        this.next = null;
    }
    public ListNode(Object data, ListNode next) {
        this.data = data;
        this.next = next;
    }
}

主方法和对应的实现方法:

public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        Reverse(node1);
    }
//prev 记录前一个元素,next 用来记录下一个元素,curr 用来记录当前的元素
    static ListNode Reverse(ListNode i) {
        ListNode prev = null, next, curr;
        curr = i;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

# 递归实现

思路:如果只有一个节点或者没有节点,那么久不需要去反转,当节点数大于等于 2 时:我们利用递归栈,先去处理掉最后一个节点,然后一个个往前返回解决,将当前节点的下一个节点的 next 指针指向当前节点,然后将当前节点的 next 释放掉。

static ListNode Recursion(ListNode i){
        if (i==null || i.next==null){
            return i;
        }
        ListNode new_node = Recursion(i.next);
        i.next.next=i;
        i.next=null;
        return new_node;
    }

执行的结果:

for (ListNode i =node1;i!=null;i=i.next){
            System.out.print(i.data+"--");
        }
        System.out.println();
// 控制台答打印的是 1--2--3--4--5--
//for 循环反转的
		ListNode a = Reverse(node1);
        for (ListNode i=a;i!=null;i=i.next){
            System.out.print(i.data+" - ");
        }
// 控制台答打印的是 5 - 4 - 3 - 2 - 1 - 
		ListNode b = Recursion(node1);
        for (ListNode i=b;i!=null;i=i.next){
            System.out.print(i.data+" - ");
        }
// 控制台答打印的是 5 - 4 - 3 - 2 - 1 -

有待更新…