代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
定义指针 p
、q
分别指向头节点和下一个节点,pre
指向头节点的前一个节点。
遍历链表,改变指针 p
指向的节点的指向,将其指向 pre
指针指向的节点,即 p.next = pre
。然后 pre
指针指向 p
,p
、q
指针往前走。
当遍历结束后,返回 pre
指针即可。
# 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:
pre, p = None, head
while p:
q = p.next
p.next = pre
pre = p
p = q
return pre
迭代版本:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null, p = head;
while (p != null) {
ListNode q = p.next;
p.next = pre;
pre = p;
p = q;
}
return pre;
}
}
递归版本:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode res = reverseList(head.next);
head.next.next = head;
head.next = null;
return res;
}
}
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
let node = head;
let pre = null;
while (node) {
let cur = node;
node = cur.next;
cur.next = pre;
pre = cur;
}
return pre;
};
func reverseList(head *ListNode) *ListNode {
if head == nil ||head.Next == nil {
return head
}
dummyHead := &ListNode{}
cur := head
for cur != nil {
tmp := cur.Next
cur.Next = dummyHead.Next
dummyHead.Next = cur
cur = tmp
}
return dummyHead.Next
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。