1、题目
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
2、思路
遍历链表,并在访问各节点时修改 next 引用指向
复杂度分析:
时间复杂度 O(N) : 遍历链表使用线性大小时间。
空间复杂度 O(1) : 变量 pre 和 cur 使用常数大小额外空间。
3、代码
class Solution { public ListNode reverseList(ListNode head) { ListNode cur = head, pre = null; while(cur != null){ ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }
4、递归方式代码
class Solution { public ListNode reverseList(ListNode head) { //结束条件 if(head == null || head.next == null){ return head; } //递 ListNode p = reverseList(head.next); //每一次执行的操作 head.next.next = head; head.next = null; //归 return p; } }