【腾讯精选练习 50 题】01—翻转链表

╰+攻爆jí腚メ 2022-10-30 01:29 329阅读 0赞

### 文章目录 ###

*   *  题目简介
     *  题目解析
     *  题目代码

## 题目简介 ##

反转一个单链表

**示例:**

`输入: 1->2->3->4->5->NULL`  
`输出: 5->4->3->2->1->NULL`

## 题目解析 ##

1.  常规面试题目，两种方法都要会，`迭代、递归`
2.  对于迭代来说：`在遍历链表时，将当前节点的 next 指针改为指向前一个节点`
3.  对于递归来说：`遍历到结尾，然后利用递归完的进行返回即可`

## 题目代码 ##

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;
        }
    }