链表逆序的两种方法(java)

public class ListNode {

int val;

ListNode next;

public ListNode(int val) {

this.val = val;

}

}

1.用迭代的方法反转链表(iteratively)

class Solution {

public ListNode reverseList(ListNode head) {

if (head == null) {

return null;

}

ListNode dummy = new ListNode(0);

dummy.next = head;

ListNode pre = dummy.next;

ListNode start = pre.next;

ListNode then = start.next;

while (then != null) {

start.next = then.next;

then.next = pre.next;

pre.next = then;

then = start.next;

}

return dummy.next;

}

}

2.用递归的方法反转链表(recursively)

class Solution {

public ListNode reverseList(ListNode head){

if (head.next == null || head == null) {

return head;

}

ListNode nextNode = head.next;

ListNode last = reverseList(nextNode);

nextNode.next = head;

head.next = null;

return last;

}

}