链表逆序
1.基础
链表是一种递归的数据结构，它或者为空，或者是指向一个结点(node)的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。
在面向对象编程中，用Java实现一个链表如下
public class Node {
Item item;
Node next;
}
下面是构造链表的过程
链表表示的是一列元素。
了解了基础内容，我们便上题：
下面是leetcode的第92题：
Reverse a linked list from positionmton. Do it in-place and in one-pass.
For example:
Given1->2->3->4->5->NULL,m= 2 andn= 4,
return1->4->3->2->5->NULL.
Note:
Givenm,nsatisfy the following condition:
1 ≤m≤n≤ length of list.
解答的代码：
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
for (int i = 0; i < m - 1; i ++)
pre = pre.next;
ListNode start = pre.next;
ListNode then = start.next;
for (int i = 0; i < n - m; i ++) {
start.next = then.next;
then.next = pre.next;
pre.next = then;
then = start.next;
}
return dummy.next;
}
}
解析：
需要有三个指针运作，很难理解，不过画图之后，就很清晰明了，本方法在反转链表时，每次start指向的下一个元素都是then的下一个元素，then的下一个元素为pre的下一个元素，pre的下一个元素，pre的下一个元素为then，然后更改then为start的下一个元素。画图如下：
