欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【Java】 剑指offer(24) 反转链表

程序员文章站 2022-07-10 13:54:40
...

本文参考自《剑指offer》一书,代码采用Java语言。

更多:《剑指Offer》Java实现合集  

题目 

  定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

思路

  方法一:使用三个指针(pre,p,next)进行实现。令p指向pre,next则是用于防止链表断裂(很简单,详见代码)。

  方法二(递归):找到最后一个结点作为返回值,递归函数中,找到最后的头结点后,开始进行每个结点next值的转换。  

测试算例 

  1.功能测试(链表有多个或一个结点)

  2.特殊测试(头结点为null)

Java代码

package _24;
/**
 * 
 * @Description 面试题24:反转链表
 *
 * @author yongh
 * @date 2018年10月15日 下午3:24:51
 */

//题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的
//头结点。

public class ReverseList {
	public class ListNode {
		int val;
		ListNode next=null;
		ListNode(int val){
			this.val=val;			
		}
	}
	
	/*
	 * 三个指针实现
	 */
	public ListNode reverseList(ListNode head) {
		if(head==null)
			return null;
		ListNode pNode=head;
		ListNode preNode=null;
		ListNode nextNode=pNode.next;
		while(nextNode!=null) {
			pNode.next=preNode;
			preNode=pNode;
			pNode=nextNode;
			nextNode=pNode.next;
		}
		pNode.next=preNode;
		return pNode;
	}
	
	/*
	 * 递归实现
	 */
	public ListNode reverseList2(ListNode head) {
		if(head==null || head.next==null)
			return head;
		ListNode rvsHead=reverseList(head.next);
		//找到了最后的头结点后,开始转换每个结点的指向
		head.next.next=head;
		head.next=null;		
		return rvsHead;
	}
	
}

  

收获

  1.与链表相关的题目总是涉及大量指针操作,以后遇到链表相关的题目时,多考虑指针的使用。

  2.递归实现时,第50行:head.next=null; 别忘记了。

  

更多:《剑指Offer》Java实现合集