翻转链表 --java实现
方法一:使用栈辅助,实现链表的翻转
package cetc.linkedtable;
import java.util.Stack;
import cetc.linkedtable.LinkedTable.ListNode;
public class LinkedTable {
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}// 链表原结构
public ListNode do_reverse(Stack<ListNode> data) {
ListNode ans = data.pop();
if (data.empty()) {
ans.next = null;
return ans;
}
ans.next = do_reverse(data);
return ans;
}// 递归反转链表核心代码:保证从栈中探出的离散元素链接成链状
public ListNode reverseList(ListNode head) {
if (head == null)
return null;
Stack<ListNode> data = new Stack<ListNode>();// 下方循环将原链表所有节点压栈,方便反转
while (true)// 循环压栈
{
if (head.next == null) {
data.push(head);
break;
}
data.push(head);
head = head.next;
}
return do_reverse(data);// 调用核心反转函数
}// 采用栈结构,调用核心反转函数代码
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedTable linkedTable = new LinkedTable();
ListNode listNode1 = linkedTable.new ListNode(1);
ListNode listNode2 = linkedTable.new ListNode(2);
ListNode listNode3 = linkedTable.new ListNode(3);
listNode1.next = listNode2;
listNode2.next = listNode3;
ListNode reverseList = linkedTable.reverseList(listNode1);
while (true) {
if (reverseList.next != null) {
System.out.println(reverseList.val);
reverseList = reverseList.next;
}else {
System.out.println(reverseList.val);
break;
}
}
}
}
方法二:使用修改头尾指针的方式
//构造链表节点
public class ListNode {
public int data;
public ListNode next;
}
//使用修改头尾指针的方式
public ListNode reverseList(ListNode pHead){
ListNode pReversedHead = null; //反转过后的单链表存储头结点
ListNode pNode = pHead; //定义pNode指向pHead;
ListNode pPrev = null; //定义存储前一个结点
while(pNode != null){
ListNode pNext = pNode.next; //定义pNext指向pNode的下一个结点
if(pNext==null){ //如果pNode的下一个结点为空,则pNode即为结果
pReversedHead = pNode;
}
pNode.next = pPrev; //修改pNode的指针域指向pPrev
pPrev = pNode; //将pNode结点复制给pPrev
pNode = pNext; //将pNode的下一个结点复制给pNode
}
return pReversedHead;
}
或者使用递归调用的方式:
//递归调用:实现链表反转
public ListNode reverseList3(ListNode pHead){
if(pHead==null || pHead.next == null){ //如果没有结点或者只有一个结点直接返回pHead
return pHead;
}
ListNode pNext = pHead.next; //保存当前结点的下一结点
pHead.next = null; //打断当前结点的指针域
ListNode reverseHead = reverseList3(pNext); //递归结束时reverseHead一定是新链表的头结点
pNext.next = pHead; //修改指针域
return reverseHead;
}