206.反转链表

• https://leetcode-cn.com/problems/reverse-linked-list

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up:

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

递归法

public ListNode reverseList(ListNode head) {

// 没有节点或者只有一个节点，不需要反转

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

ListNode newHead = reverseList(head.next);

head.next.next = head;

head.next = null;

return newHead;

}

迭代法

public ListNode reverseList(ListNode head) {

ListNode newHead = null;

ListNode originalNext;

while (head != null) {

originalNext = head.next;

head.next = newHead;

newHead = head;

head = originalNext;

}

return newHead;

}

info

也可以理解为preNode和nextNode两个指针，next指向pre，依次向前移动

• 为了移动，需要记录nextNode的next域
• nextNode移动后，preNode变为原先的nextNode，就是向前移动了

public ListNode reverseList(ListNode head) {

ListNode nextNode = head;

ListNode preNode = null;

ListNode originalNext;

while (nextNode != null) {

originalNext = nextNode.next;

nextNode.next = preNode; // 后一个指向前一个

preNode = nextNode; // 移动

nextNode = originalNext; // 按原先的下一个移动

}

return preNode;

}

测试代码

public static void main(String[] args) {

ListNode listNode1 = new ListNode(1);

ListNode listNode2 = new ListNode(2);

ListNode listNode3 = new ListNode(3);

ListNode listNode4 = new ListNode(4);

listNode1.next = listNode2;

listNode2.next = listNode3;

listNode3.next = listNode4;

listNode4.next = null;

LinkedListUtils.print(listNode1);

ListNode reverseHead = new _206反转链表().reverseList(listNode1);

LinkedListUtils.print(reverseHead);

}

1 -> 2 -> 3 -> 4 -> null

4 -> 3 -> 2 -> 1 -> null