Java如何翻转链表
本篇内容介绍了“Java如何翻转链表”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
创新互联建站-专业网站定制、快速模板网站建设、高性价比来宾网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式来宾网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖来宾地区。费用合理售后完善，10多年实体公司更值得信赖。
package com.lifeibigdata.algorithms.leetcode;
/**
* Created by lifei on 16/6/30.
*/
public class ReverseListNode {
public static void main(String[] args) {
ListNode head=new ListNode(1);
ListNode n1 =new ListNode(2);
ListNode n2 =new ListNode(3);
ListNode n3 =new ListNode(4);
//初始化链表
head.next = n1 ;
n1.next = n2;
n2.next = n3;
System.out.println("打印链表反转前：");
Utils.print(head);
ReverseListNode rln = new ReverseListNode();
System.out.println("打印链表反转后：");
ListNode newHead = rln.reverse4(head);//TODO 3种方式
Utils.print(newHead);
// System.out.println("===========create==============");
// ListNode cln = createList(new int[]{1,2,3,4,5});
// Utils.print(cln);
}
/**
* 第一轮
* 3.next (reverse) revHead 4
* 3.next.next=4.next(赋值前为null) 3
* 3.next -> null
* 4 3 null
*
*第二轮
* 2.next.next=3.next(赋值前为null) 2
* 2.next -> null
* 4 3 2 null
*
*
*
* @param head
* @return
*/
ListNode reverse(ListNode head){
if (null == head || null == head.next){//TODO 如果是终节点,就会将终结点返回,所以revHead就是终结点
return head;
}
ListNode revHead = reverse(head.next);
System.out.println("----"+head.val+","+head.next.val+"----");
head.next.next = head; //3.next.next(4.next，此时4是翻转后的头结点)=3
head.next = null; //3.next=null
return revHead;
}
//“头插法”思想描述：从链表的第一个结点开始，以每一个结点为单位，遍历链表，将遍历到的结点依次插入到头结点的后面
ListNode reverse2(ListNode head){//TODO
if (null == head || null == head.next) {
return head;
}
ListNode pre = null; //新链表过程中的头结点
ListNode cur = head; //cur为遍历的游标,同时也是最后返回链表的头结点
ListNode next = cur.next;
while (next != null){ //todo cur为即将插入的节点,此处是判断循环终止的条件
cur.next = pre; //将待插入的节点->新链表的头结点
pre = cur; //将新插入的节点,作为下一次循环的头结点
cur = next; //循环下一个节点
next = cur.next; //判断新节点的下一个节点,进行循环
}
cur.next = pre;
return cur;
}
//头插法
static ListNode reverse3(ListNode head) {
if (null == head || null == head.next) {
return head;
}
ListNode nextHead = null; //待转置的下一个节点
ListNode newHead = null; //新链的头节点
ListNode newn = null; //待插入插入的节点 需要待插入的节点直接指向新链的头节点，那么返回新插入的节点，就是插入之后链的头节点
newHead = head; //把旧头结点赋值给新头结点
head = head.next; //此时的head已经是第二个节点
newHead.next = null;
while(head.next != null){ //此时的head是第二个节点,该节点为需要加入链表的新节点，即newn; head.next第三个节点,，
nextHead = head.next; //下一次待转置的节点
newn = head; //将要插入的新节点
newn.next = newHead; //新插入的节点指向 新链的头节点
newHead = newn; //将新插入的节点作为新链的节点
// newn.next = newHead.next; //错误的 不能用创建链表的方式，因为创建链表的方式有一个空的头节点
// newHead.next = newn; //错误的
head = nextHead;
}
newn = head; //因为每次判断的是新插入节点的下一个节点，所以最后一个节点不在循环中，此时的head就是最后一个节点
newn.next = newHead;
return newn;
}
ListNode reverse4(ListNode L){//TODO
ListNode head = null;
ListNode temp ;
while (L != null){
temp = L.next;//将第二个节点赋值给tmp
L.next = head;//将第一个节点指向新的头结点
head = L; //将新的头结点L赋值给head,用于下次循环
L = temp; //下一次迭代中迭代的是第二个节点
}
return head;
}
/**
* 图示
* @param head
* @return
*/
ListNode reverse5(ListNode head){//TODO
ListNode pRerverseHead = null;
ListNode pNode = head;
ListNode pPrev = null;
while (pNode != null){
ListNode next = pNode.next;
if (next == null){
pRerverseHead = pNode;
}
pNode.next = pPrev;
pPrev = pNode;
pNode = next;
}
return pRerverseHead;
}
static ListNode createList(int[] values){
ListNode head = new ListNode(0);
for(int i = 0;i < values.length;i++){
ListNode node = new ListNode(values[i]);//新节点node
node.next = head.next;//将头节点的尾部转移到新节点的尾部
head.next = node;//将头结点尾部指向新节点
}
return head.next;
}
/**
*
*
打印链表反转前：
1->2->3->4->
打印链表反转后：
----4,3----
----3,2----
----2,1----
4->3->2->1->
*/
} “Java如何翻转链表”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
网站标题：Java如何翻转链表
当前URL：http://scyanting.com/article/jdsdgs.html
