反转链表.md

题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

链表节点定义如下：

public class ListNode {
    int val;
    ListNode next = null;
}

测试用例

• 功能测试（输入的链表含有多个节点；链表中只有一个节点）
• 特殊功能测试（链表头节点为空指针）

题目考点

• 考察应聘者对链表、指针的编程能力
• 考察应聘者思维的全面性及写出来的代码的鲁棒性

解题思路

主要的过程有以下三步：

1. 定义一个将指向反转链表的头指针和一个保存临时节点的指针
2. 循环头节点的下一个节点，如果不为空，则将它的下一个节点作为新的头结点，并用临时节点保存之前头节点
3. 然后就是链表的重排问题了，首先原链表的头结点，将指向的新的头节点的下一个节点，新的头节点将指向原来的头结点

自己解题

/**
 * 反转链表
 *
 * @Author rex
 * 2018/7/28
 */
public class Solution {
    /**
     * 自己解法
     * @param head
     * @return
     */
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode currHead = head;
        ListNode temp = null;
        while (head.next != null) {
            temp = currHead;
            currHead = head.next;
            head.next = head.next.next;
            currHead.next = temp;
        }
        return currHead;
    }
}

参考解题

同自己解题

补充

自已多花时间找出问题并修正问题比在面试官找出问题再去慌慌张张修改代码要好很多。其实面试官检查应聘者所写代码的方法也是用他事先准备好的测试用例来进行测试。如果应聘者能够想到这些测试用例，并用它们来测试自己的代码，就能保证有备无患了。