【leetcode】【初级算法】【链表3】反转链表

题目

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

示例 1：

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

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnnhm6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解（两种方法）

    // 两种方法 ：
    // 方法一：遍历 用三个指针 prev cur nextTemp
    // 方法二：递归 注意反转之后首节点的next指针为null （None （python中））
1
2
3

方法一：遍历

java题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

        // 第一步 定义prev节点
        ListNode prev = null;
        // 第二步 定义cur
        ListNode cur = head;
        // 第三步 遍历 
        while(cur!=null){
            ListNode nextTemp = cur.next;
            // 做反转
            cur.next = prev;
            // 移动prev指针，为下一节点做准备
            prev = cur;
            // 移动cur指针，为下一节点做准备
            cur = nextTemp;
                      
        }
        // 返回最前节点
        return prev;

    }
}
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
28
29
30
31
32
33

py解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 方法一 遍历
        pre = None
        while head:
            nextTemp = head.next
            # 反转
            head.next = pre
            # 移动pre和head（表示当前操作节点），为下一次做准备
            pre,head = head,nextTemp
        return pre

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：递归

java解：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归
        // 返回条件
        if(head==null||head.next==null){
            return head;
        }
        // 假设后面都已经反转好了，
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24