NO.206 翻转链表 简单
本题是K个一组翻转链表这道题的其中一步，学习完本题可以趁热打铁学习NO.25，题解参考徒手挖地球十八周目。
思路一：迭代实现 翻转链表需要三个”指针”：pre指向前驱、curr指向当前节点、next指向后继。
过程比较简单，自己模拟一遍就好了：
1
2
3
4
5
6
7
8
9
10
11
| public ListNode reverseList(ListNode head) {
if (head==null||head.next==null)return head;
ListNode pre=null,curr=head;
while (curr!= null) {
ListNode next=curr.next;
curr.next=pre;
pre=curr;
curr=next;
}
return pre;
}
|
时间复杂度：O(n)
思路二：递归实现 每层递归返回已经翻转好的部分。
1
2
3
4
5
6
7
| public ListNode reverseList(ListNode head) {
if (head==null||head.next==null)return head;
ListNode pre=reverseList(head.next);
head.next.next=head;
head.next=null;
return pre;
}
|
时间复杂度：O(n)
本人菜鸟，有错误请告知，感激不尽！
更多题解和学习记录博客:博客、github