题目
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
实现
思路：利用双指针的方式
p1作为前面的指针探路，p2作为后面的指针跟进，顺着链表跑一圈，搞定问题。
C# 语言
- 状态：通过
- 27 / 27 个通过测试用例
- 执行用时: 116 ms, 在所有 C# 提交中击败了 97.50% 的用户
- 内存消耗: 23.3 MB, 在所有 C# 提交中击败了 5.26% 的用户
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution
{
public ListNode ReverseList(ListNode head)
{
if (head == null || head.next == null)
return head;
ListNode p1 = head;
ListNode p2 = null;
while (p1 != null)
{
ListNode temp = p1.next;
p1.next = p2;
p2 = p1;
p1 = temp;
}
return p2;
}
}
Python 语言
- 执行结果：通过
- 执行用时：36 ms, 在所有 Python3 提交中击败了 92.27% 的用户
- 内存消耗：14.6 MB, 在所有 Python3 提交中击败了 17.65% 的用户
# 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:
if head is None or head.next is None:
return head
p1 = head
p2 = None
while p1 is not None:
temp = p1.next
p1.next = p2
p2 = p1
p1 = temp
return p2