题目:
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]
双指针法:
两个指针,cur指向当前节点,用来遍历,pre指向上一节点。
null | 1 | 2 | 3 | 4 | 5 |
pre | cur |
cur在前面走,把指针甩向上一节点。最终返回反转链表头结点pre。
1 | 2 | 3 | 4 | 5 | null |
pre | cur |
class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; ListNode temp = null; while (cur != null) { temp = cur.next;// 保存下一个节点 cur.next = pre;// 当前节点指向前一节点 //往前走一步 pre = cur; cur = temp; } return pre;//此时pre指向反转链表头结点,返回反转后的链表 } }
递归法:
class Solution { public ListNode reverseList(ListNode head) { return reverse(null,head);//第一层:pre=null,cur=head } public ListNode reverse(ListNode pre, ListNode cur){ if(cur==null){ return pre;//返回反转链表 } ListNode temp=null; temp=cur.next; cur.next=pre; return reverse(cur,temp);//第n层:pre=cur,cur=temp } }
标签:pre,力扣,head,ListNode,cur,206,链表,null From: https://www.cnblogs.com/cjhtxdy/p/16886663.html