206. 反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

难度：🌟🌟

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

题解

假设给定反转链表序号如下： 1->2->3->4->5->null
第一步应该在节点1前加上虚拟头节点 dummyHead
接下来是交换1和2的位置，值得注意的是，2应该指向 dummyHead.Next，dummyHead.Next 也应该指向2。
以次类推，直到遍历完链表。

代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 迭代方式
func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	dummyHead := &ListNode{Val: -1}
	dummyHead.Next = head
	p := dummyHead.Next
	for p.Next != nil {
		next := p.Next
		second := next.Next
		next.Next = dummyHead.Next
		dummyHead.Next = next
		p.Next = second
	}
	return dummyHead.Next
}

// 递归方式
func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

递归方式说明

/**
 * 以链表1->2->3->4->5举例
 * @param head
 * @return
 */
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
    /*
            直到当前节点的下一个节点为空时返回当前节点
            由于5没有下一个节点了，所以此处返回节点5
    */
    return head;
    }
    //递归传入下一个节点，目的是为了到达最后一个节点
    ListNode newHead = reverseList(head.next);
    /*
            第一轮出栈，head为5，head.next为空，返回5
            第二轮出栈，head为4，head.next为5，执行head.next.next=head也就是5.next=4，
                                把当前节点的子节点的子节点指向当前节点
                                此时链表为1->2->3->4<->5，由于4与5互相指向，所以此处要断开4.next=null
                                此时链表为1->2->3->4<-5
                                返回节点5
            第三轮出栈，head为3，head.next为4，执行head.next.next=head也就是4.next=3，
                                此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3.next=null
                                此时链表为1->2->3<-4<-5
                                返回节点5
            第四轮出栈，head为2，head.next为3，执行head.next.next=head也就是3.next=2，
                                此时链表为1->2<->3<-4<-5，由于2与3互相指向，所以此处要断开2.next=null
                                此时链表为1->2<-3<-4<-5
                                返回节点5
            第五轮出栈，head为1，head.next为2，执行head.next.next=head也就是2.next=1，
                                此时链表为1<->2<-3<-4<-5，由于1与2互相指向，所以此处要断开1.next=null
                                此时链表为1<-2<-3<-4<-5
                                返回节点5
            出栈完成，最终头节点5->4->3->2->1
    */
    head.next.next = head;
    head.next = null;
    return newHead;
}