By

文章目录
  1. 1. Reverse Linked List
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题

Reverse Linked List

题目

Reverse a singly linked list.

Hint:

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

思路

头插法 cur和pre分别表示当前结点和当前结点的前一结点，dummy.next=head;按照如下操作，不断将当前结点插入到头结点处。

pre->next=cur->next;
cur->next=dummy->next;
dummy->next=cur;
cur=pre->next;

解题

C++版

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

Python 版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def reverseList(self, head):
        if not head:
            return None
        dummy=ListNode(0)
        dummy.next=head
        pre=head
        cur=pre.next
        while(cur):
            pre.next=cur.next
            cur.next=dummy.next
            dummy.next=cur
            cur=pre.next
        return dummy.next

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head)
            return NULL;
        if(!head->next)
            return head;
        ListNode *newHead=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return newHead;
    }
};
leetcode
leetcode,linkList
文章目录
  1. 1. Reverse Linked List
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题