题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
递归思想如下:
Java代码如下:
public class ListNode {
int val;
ListNode next=null;
public ListNode(int x) {
val=x;
}
}
class Solution{
//迭代循环实现
public ListNode reverseList(ListNode head) {
ListNode preNode=null;
ListNode curNode=head;
while(curNode!=null) {
//保存当前结点的下一个结点
ListNode nextNode=curNode.next;
//将当前结点的next域指向它的前一个结点
curNode.next=preNode;
//结点指针向后移
preNode=curNode;
curNode=nextNode;
}
//返回头节点
return preNode;
}
//递归方法实现
public ListNode dgReverseList(ListNode head) {
if(head==null||head.next==null)return head;//如果是空链表或者单个结点的链表,直接返回
ListNode nextNode=dgReverseList(head.next);//指向最后一个结点
//与下一个结点交换
head.next.next=head;
head.next=null;
return nextNode;
}
}