反转链表 Posted on 2021-07-10 00:00:00 2021-07-10 00:00:00 by Author 摘要 给一个单链表的头节点head，你能原地反转该链表吗？？？？？？ # 反转链表 1. 题目描述：给你单链表的头节点 `head` ，请你反转链表，并返回反转后的链表。 2. 示例描述： - 示例一： - 输入：1->2->3->4 - 输出：4->3->2->1 - 示例二： - 输入：1->2 - 输出：2->1 3. 解题思路： - 对于反转链表，需要定义一个新的一个指向头节点的指针，这是因为要反转链表，需要记录已经反转链表的头节点（就地反转）,同时定义两个工作指针，一个指向当前需要反转的链表的节点，一个指向需要反转节点的下一个节点，定义这两个指针目的是为了记录未反转节点的头节点的位置，同时保证整个链表的所有节点都能够顺序的反转。具体细节见代码注释 4. 代码实现： ```java public ListNode reverseList(ListNode head) { //如果链表为空，直接返回空链表 if (head == null) { return head; } //定义一个指向链表头节点的节点，和两个工作指针，分别指向头节点和头节点的下一个节点 ListNode tempHead = new ListNode(), point = head, temp = head.next ; tempHead.next = null; //如果工作指针未到达链表尾部,反转链表 while (temp != null) { //先断链，第一个工作工作指针链接以前反转过的节点的头部(精华部分) point.next = tempHead.next; //在接链,定义的头指针链接当前反转的节点,以便下次继续进行反转操作 tempHead.next = point; //两个工作指针分别后移以为 point = temp; temp = temp.next; } //第二个工作指针已经到链表尾部，但是需要反转的节点指针， // 指向原始链表的尾部，所以该节点需要反转到反转后节点的头部 point.next = tempHead.next; tempHead.next = point; //最后返回反转后节点的头指针 return tempHead.next; } ```
{{ item.content }}
{{ child.content }}