LeetCode 92 & 206. Reverse Linked List

题目206. Reverse Linked List 题意：将单链表反转 思路：从头节点开始指针逆转 具体实现见下面代码：

public class LeetCode206 { public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public ListNode reverseList(ListNode head) { if(head == null) return head; else{ ListNode cur = head; ListNode p = head.next; cur.next = null; //反转之后头指针指向空，很重要！！！ while( p != null){ System.out.println(p.val); ListNode q = p.next; p.next = cur ; cur = p; p = q; } return cur; } } }

题目92. Reverse Linked List II 题意：将单链表中一段进行反转 例如1->2->3->4->5->6 中2到4进行反转，则可以拆分为l1(1),l2(2->3->4),l3(5->6)三部分，然后对l2进行反转，然后对三者进行拼接 具体实现思路如下：

public class LeetCode92 { public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public ListNode reverseBetween(ListNode head, int m, int n) { if(head==null || head.next==null || m >= n) return head; ListNode nhead = new ListNode(0); nhead.next = head; ListNode start = nhead; ListNode end = null; int count = 0; while(start.next != null && count < m - 1){ count++; start = start.next; } // 执行完while，此时start位于1处，即l1的最后一个元素 ListNode sta1 = start.next; // sta1即为l2的第一个元素 ListNode end2 = sta1; // 保存l2的第一个元素 ListNode a = null; ListNode b = null; // 反转l2 while(sta1 != null && count < n){ b = sta1.next; sta1.next = a; a = sta1; sta1 = b; count++; } //拼接三者 start.next = a; end2.next = b; return nhead.next; } }