链表-Reverse Linked List(反转单向链表)

时间:2022-08-09 19:42:56

问题描述:

Reverse a singly linked list.

click to show more hints.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

思考:

用遍历和递归两种方式实现,使用遍历很好理解,考虑使用三个索引,分别为头head,头后面的一个Next和Next后面的nextNext,head的next为空不说了,关键在每一次访问中的Next的next引用需要变化,但是又是单项链表next变化,后面的节点就找不到了,这就是nextNext的作用。然后是使用递归,参考了别人的例子,用只有两个节点的特殊链表就可以轻松理解。

代码(java):

1.遍历
public ListNode reverseList(ListNode head) {


if(head == null || head.next == null){
return head;
}


ListNode next;
ListNode nextNext;
next = head.next;
nextNext = next.next;


head.next = null;

while(nextNext!=null){
next.next = head;



head = next;
next = nextNext;
nextNext = nextNext.next;
}

next.next = head;
head = next;

return head;
}

2.递归
public ListNode reverseList(ListNode head) {
if(head==null) return null;
if(head.next==null) return head;

ListNode p = head.next;
ListNode n = reverseList(p);

head.next = null;
p.next = head;
return n; //递归求法
}