剑指offer24-反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 限制： 0 <= 节点个数 <= 5000

这里给出两种思路，一是双指针头插法建立链表，二是利用递归

双指针

# 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: newHead=None; while head!=None: p=head.next head.next=newHead newHead=head head=p return newHead

递归

递归函数返回反转后链表的头结点，再将原链表的头结点加入反转链表

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { if(!head||!head.next) return head; let ret=reverseList(head.next); head.next.next=head; //head.next是新链表的尾节点 head.next=null; return ret; };