链表的反转

问题重述：

创建两个函数，分别实现反转单向链表和双向链表，给予链表的头节点head，返回反转后的头结点

要求：如果链表的长度为n，时间复杂度要求为o（n），空间复杂度为o（1）

问题分析：

题目要求我们反转，我们可以直接循环链表，然后在循环体中对每一个结点进行反转，需要注意的是，我们不能直接反转，需要借用新的结点来辅助操作，否则的话会导致后续结点丢失

解法：

迭代

解题：

代码：

public static Node reverseLinkedList(Node head) {
		Node next = null;
		Node pre = null;
		while(head != null) {
			next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		
		return pre;
	}
	public static DoubleNode reverseDoubleLinkedList(DoubleNode head) {
		DoubleNode next = head.next;
		DoubleNode pre = null;
		while(head != null) {
			next = head.next;
			head.next = pre;
			head.pre = next;
			pre = head;
			head = next;
		}
		
		return pre;
	}

代码解析：

创建两个结点，分别用于记录当前节点的前一个结点和后一个结点，然后循环链表，每经过一个结点，就将当前结点的next指向前一个结点，然后将当前结点作为下一个结点的前一个结点记录下来，将结点后移，不断循环，直到结束。

总结：

对于链表的操作，如果和头节点有关，我们可以使用dummy结点来简化操作，如果没有的话，一般直接遍历就可以，如果有必要的话就创建结点保存结点的前一个结点和后一个结点来简便操作