【剑指Offer】015——反转链表 （链表）

题目描述

输入一个链表，反转链表后，输出新链表的表头。

解题思路

设置三个指针，head为当前节点，pre为当前节点的前一个节点，next为当前节点的下一个节点，需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2的过程中，用pre让节点反转所指方向，next节点保存next1节点防止链表断开

需要注意的点：
1、如果输入的头结点是null，则返回null
2、链表断裂的考虑

参考代码

Java

class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null)
            return null;
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next; // 保存下一个结点
            head.next = pre;  // 重新指定方向(第一次指向空)
            pre = head;       // 获取
            head = next;      // 新的head
        }
        return pre;
    }
}

Python

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        if pHead is None:
            return None
        pre,nex = None, None
        while pHead is not None:
            nex = pHead.next  # 获取下一个
            pHead.next = pre    # 更改方向
            pre = pHead    # 更新前一个
            pHead = nex    # 获取新的pHead
        return pre

个人订阅号

image