算法通关村第二关——链表反转

算法通关村第二关——链表反转"/>

算法通关村第二关——链表反转

1、简历虚拟头节点辅助反转

        链表如下：

 联立虚拟节点：ListNode ans = new ListNode（-1），且ans.next = head.

此时 

 算法的关系来了，就是我们需要设一个变量ListNode cur = head;

ListNode temp = cur.next;
cur.next = ans.next;
ans.next = cur;
cur = next;

这完成了第一次反转

第二次

依次执行就可以反转链表。

完整代码如下：

public static ListNode reverseList(ListNode head){ListNode ans = new ListNode(-1);ListNode cur = head;while(cur!=null){ListNode temp = cur.next;cur.next = ans;ans.next = cur;cur = temp;}return ans.next;
}

 2.直接操作链表实现反转

        直接转变链表的方向,看图。

public static ListNode reverseList(ListNode head){ListNode ans = null;ListNode cur = head;while(cur!=null){ListNode temp = cur.next;cur.next = ans;ans = cur;cur = temp;}return ans;
}