Java如何翻转链表

66次阅读
没有评论

共计 3429 个字符,预计需要花费 9 分钟才能阅读完成。

本篇内容介绍了“Java 如何翻转链表”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让丸趣 TV 小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

package com.lifeibigdata.algorithms.leetcode;

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=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 如何翻转链表”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注丸趣 TV 网站,丸趣 TV 小编将为大家输出更多高质量的实用文章!

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-08-16发表,共计3429字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)