题解 | #反转链表#
反转链表
http://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca
Leetcode有对应的视频，更容易理解。
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode* cur = pHead;
ListNode* pre = nullptr;
ListNode* nxt = nullptr;
while(cur){
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
};
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre, cur = None, head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
以Python代码为例说明：
需要三个指针：pre, cur, nxt，分别对应未反转链表的时候前一个结点、当前节点、下一个节点。
nxt = cur.next，先让nex指向下一个节点，也就是记录下一个节点的位置。cur.next = pre，当前节点的next指针，指向前一个节点pre，这里实现链表反转。pre = cur，前一个节点pre移动到当前节点。cur = nxt，当前节点cur移动到下一个节点。
最后的时候，cur指针指向NULL，退出循环，此时pre指向未反转链表的最后一个元素，正好是反转链表的第一个元素。返回pre即可。
查看22道真题和解析