LeetCode 206

题目描述：反转链表

 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

例如：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

 方法一：边遍历原链表，边创建一个新链表（题目中没有对空间复杂度的要求），头插法插入即可。

addFirst(5->4->3->2->1);

如下图所示：

代码实现：

package LeetCode;public class Num206 {//头插法public ListNode reverseList(ListNode head) {if (head == null || head.next == null){//如果原链表为空，返回head也为空；如果原链表的后继为空，返回head就是head节点return head;}//新链表的虚拟头节点ListNode dummyHead = new ListNode(5001);//边遍历原链表，边头插新链表while(head != null){//创建新节点使得新节点的值等于原链表头节点的值ListNode node = new ListNode(head.val);node.next = dummyHead.next;dummyHead.next = node;head = head.next;}//返回新链表的头节点，即虚拟节点的后继return dummyHead.next;}
}

方法二：原地移动法，当题目要求空间复杂度为O(1)时，只能改变原链表的指向。

注意：回文链表只是原链表的next不再指向后继转而指向前驱。

我们可以引入两个引用：

• cur->表示当前需要处理的节点
• prev->表示当前节点的前驱，cur.next = prev;
• next->next = cur.next，用来暂存下一个需要处理的节点。

如图所示： 

    //原地移动法public ListNode reverseList(ListNode head){if (head ==null || head.next == null){return head;}ListNode prev = null;//cur表示当前需要反转的节点ListNode cur = head;while(cur != null){ListNode next = cur.next;cur.next = prev;prev = cur;cur = next;}return prev;}

方法三：传入一个以head为头节点的链表，reverseList（）方法就可以将次链表反转并且返回反转后链表的头节点。

 代码实现：

    //递归法public ListNode reverseList(ListNode head){//1、判空if (head ==null || head.next == null){return head;}ListNode sec = head.next;//2、反转第二个节点之后的子链表ListNode newHead = reverseList(head.next);//3、处理head与sec关系sec.next = head;head.next = null;return  newHead;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！