java反转链表的多种解决方法举例详解_Java

反转链表的三种方式

1，使用栈解决

栈是最容易的一种方式了，因为栈是先进后出。实现原理就是把链表节点一个个入栈，全部入栈之后再一个个出栈，出栈的时候在把节点按照出栈的顺序组成一个新的链表。

原理如图：

代码如下：

public listnode reverselist(listnode head){
	stack<listnode> stack = new stack<>();
	//把全部节点都压入栈中
	while(head != null){
		stack.push(head);
		head = head.next;
	}
	//如果stack栈里面没有数据，说明head是一个空指针，因此可以直接返回
	//不需要进行后续计算
	if(stack.isempty()){
		return null;
	}
	listnode node = stack.pop();//出栈的第一个节点成为第一个新链表的第一个节点
	listnode dummy = node; //保留头节点，用于最后的返回
	//把栈中的节点全部出栈，然后重新连成一个新的链表
	while(!stack.isempty()){
		node.next = stack.pop();
		node = node.next;//更换链表的最后一个元素
	}
	//最后一个节点就是反转前的头节点，需要让他的next为null
	//不然可能构成环
	node.next = null;
	return dummy;//最后返回保存好的头节点
}

2，双指针实现

利用两个指针来保存链表中数据，一个指针用来存储当前节点中next元素中更改后的值，另一个指针来指向下一个需要更改节点的地址。

原理如图：

代码如下：

public listnode reverselist(listnode head) {
	//当前节点中next元素改变后的值
	//初始值为null是因为更改后 原第一个元素 改后最后一个元素
	//next指向的值为null
	listnode changenode = null;
	while (head != null) {
	    //先保存当前访问的节点的下一个节点
		//留着while循环最后更新数据并且
		listnode nextnode = head.next;
		//把当前节点中next元素进行更改，使其可以指向前一个元素
		head.next = changenode;
		//更新changenode指针，用于下一次节点next元素更新
		changenode = head;
		//更新节点，去往下一个节点
		head = nextnode;
	}
	//循环之后changenode指向的值为 原最后一个节点 改后第一个节点
	//所以返回changenode就是改后的头节点
	return changenode;
}

3，递归实现

递归实现是最难的，理由是递归本身很难理解。我认为递归的本质是通过不断的改变参数找到问题的原点，再进行返回。逻辑处理部分则是在不断找寻原点的过程中，或者是找到原点后在返回的过程中进行的。这个题目既可以在找原点的过程中设置逻辑处理，也可以在返还的过程中进行逻辑处理。

找原点的过程中设置逻辑处理：

public listnode reverselist(listnode head) {
    //reverse函数的两个参数的意思是，当前节点和上一个节点
    //head是原本函数的头节，null是更改后头节点指向的值
    return reverse(head, null);
}

public listnode reverse(listnode nownode, listnode lastnode) {、
    //当前节点是null
    //说明上一个节点是最后一个节点
    if (nownode == null) { 
        return lastnode;  
    }
    //先保存下一个地址的位置
    listnode next = nownode.next;
    //让当前节点指向上一个节点
    nownode.next = lastnode;

    //处理完这个节点的逻辑之后开始前往下一个节点
    return reverse(next, nownode);
}

返还的过程中进行逻辑处理：

	public listnode reverselist(listnode head){
		//当前节点的next元素没有指向下一个元素的时候说明这是最后一个元素
		if(head == null || head.next == null){
			return head;
		}
		//找到最后一个元素，并开始一层一层的往上传递
		listnode last = reverselist(head.next);
		//把下一个元素指向的元素改为自己
		//（因为递归条件的影响当前的元素只可能是反转后第二个元素之后的元素，
		// 所以head.next.next不会越界）
		head.next.next = head;
		//并且清除当前指向的节点，防止可能的问题（成环）
		head.next = null;
        //传递最后一个元素
		return last;
	}

建议先看懂前面两个方法再来看最后的递归，先看懂这个题目的基本处理逻辑。

后面两个解法的本质是指针的运用，java对这方面没有很好的解释，所以可能会有点难理解