题目简介
反转一个单链表
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
题目解析
- 常规面试题目，两种方法都要会，
迭代、递归 - 对于迭代来说：
在遍历链表时，将当前节点的 next 指针改为指向前一个节点 - 对于递归来说：
遍历到结尾，然后利用递归完的进行返回即可
题目代码
public class Study01 { // 递归 public ListNode reverseListRecursion(ListNode head) { // 防止head为空或者一个的情况 if(head == null || head.next == null){ return head; } ListNode newNode = reverseListRecursion(head.next); // 将当前head的next.next指向当前元素 head.next.next = head; head.next = null; return newNode; } // 迭代 public ListNode reverseListIteration(ListNode head) { if(head == null){ return null; } ListNode p1 = null; ListNode p2 = head; ListNode p3 = null; while(p2 != null){ // 让p3去占领下一个位置 p3 = p2.next; p2.next = p1; p1 = p2; p2 = p3; } return p1; } }
