LeetCode 206 Reverse Linked List

Problem:

Reverse a singly linked list.

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

Summary:

翻转链表。

Analysis:

1. Iterative solution

1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* reverseList(ListNode* head) { 12 ListNode *pre = NULL; 13 14 while (head != NULL) { 15 ListNode *tmp = head->next; 16 head->next = pre; 17 pre = head; 18 head = tmp; 19 } 20 21 return pre; 22 } 23 };

 2. Recursive solution

若链表为n₁->n₂->...->n_k-1->n_k->n_k+1->...->n_m->NULL

假设n_k+1到n_m的部分已翻转：n₁->n₂->...->n_k-1->n_k->n_k+1<-...<-n_m

我们若要使n_k+1的next指针指向n_k，则我们需要做的是：n_k->next->next = n_k

需要注意的是需要将n₁的next指针指向NULL。

1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* reverseList(ListNode* head) { 12 if (head == NULL || head->next == NULL) { 13 return head; 14 } 15 16 ListNode *tmp = reverseList(head->next); 17 head->next->next = head; 18 head->next = NULL; 19 20 return tmp; 21 } 22 };

 

Reference: https://leetcode.com/articles/reverse-linked-list/#approach-1-iterative-accepted

转载于:https://www.cnblogs.com/VickyWang/p/6012874.html

相关资源：JAVA上百实例源码以及开源项目