首页 > Java > java教程 > 链表常用操作——反转详解

链表常用操作——反转详解

零下一度
发布: 2017-07-19 13:40:50
原创
2067 人浏览过

链表常用操作——反转

我们先来定义一个单链表的节点类

public class ListNode {2         
int val;3         ListNode next = null;// 指向的下个节点4 5         
ListNode(int val) {6             this.val = val;7         }8     
}
登录后复制

 

实现单链表反转共有两种方法

1、使用递归,从后往前反转。从头结点开始,往后查找直到找到尾节点为止,然后开始反转。  

 1     public ListNode reverseList(ListNode head) { 2         
 if (head == null || head.next == null) 3             return head; 4  5         
 ListNode prev = reverseList(head.next);// 递归调用,先反转下个节点 6  7         
 head.next.next = head;// 将当前结点的指针域指向前一结点 8         
 head.next = null;// 前一结点的指针域令为null; 9         
 return prev;// 反转后新链表的头结点10     
 }
登录后复制

 

2、使用遍历,从前往后反转。先保存下个节点,然后将将当前节点指向前个节点,然后在将节点向下移动继续循环进行下次反转。

 1     public ListNode reverseList(ListNode head) { 2         if (head == null) { 3             
 return null; 4         } 5         ListNode pre = null; 6         
 ListNode next = null; 7         while (head != null) { 8             
 // 保存下个节点,防止丢失 9             next = head.next;10             
 // 将他的下个节点指向前个节点11             head.next = pre;12 13             
 // head指向pre后,就继续依次反转下个节点14             
 // 让pre,head依次向后移动一个节点,继续下一次的反转15             
 pre = head;16             head = next;17         }18         
 return pre;19     
 }
登录后复制

刚做完在线编程,就随手记录下来,方便日后查看。

以上是链表常用操作——反转详解的详细内容。更多信息请关注PHP中文网其他相关文章!

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板