LeetCode 206.反转链表

这是一道关于链表最基础也是最经典的一道题目，就是我们需要反转一个链表，题目如下所示：
LeetCode 206.反转链表
这道题的思想就是我们需要把链表中每个节点所指的方向调转，然后把指针往后移，一直到链表尽头，整个流程可以如下所示：

我们这里有三个指针，分别表示前一个位置 prev，当前位置 cur 和下一个位置 next。每次操作的第一步就是将prev指向cur的指针方向调转，然后移动向下一个位置移动cur指针，直到cur到链表的末尾，那么我们就可以用以下代码来实现。
首先是java版本：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            // 调转指针方向
            cur.next = pre;
            // 移动指针位置
            pre = cur;
            cur = next;
        }
        return head;
    }
}

然后是python版本：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, prev = head, None
        while cur:
        	# 调转指针方向，移动指针位置
            cur.next, prev, cur = prev, cur, cur.next
        return prev

这么一来链表就反转了，这也是链表的基本操作。

LeetCode 206.反转链表

相关推荐