【算法】翻转链表206

206. 反转链表 - 力扣（Leetcode）

双指针法

public class ReverseLinkedList206 {
	public static void main(String[] args){
		ListNode head = initLinkedList(new int[]{1,2,3,4,5});
		printLinkedList(head);
		printLinkedList(reverseList(head));
	}

	//双指针法
	public static ListNode reverseList(ListNode head) {
		if (head == null) {
			return null;
		}
		ListNode pre = null;
		ListNode cur = head;

		ListNode nextNode;
		while(cur != null){
			nextNode = cur.next;
			cur.next = pre;
			pre = cur;
			cur = nextNode;
		}
		return pre;
    }

  
    public static ListNode initLinkedList(int[] nums){
    	ListNode head = new ListNode(nums[0]);
    	ListNode cur = head,node;
    	for(int i = 1; i < nums.length; i++){
    		node = new ListNode(nums[i]);
    		cur.next = node;
    		cur = node;
    	}
    	return head;
    }
     public static void printLinkedList(ListNode head){
    	ListNode cur = head;
    	while(cur != null){
    		System.out.print(cur.val + "->");
    		cur = cur.next;
    	}
    	System.out.println();
    }
}
class ListNode {
	int val;
	ListNode next;
	public ListNode(){}
	public ListNode(int val){this.val = val;}
	public ListNode(int val, ListNode next){
		this.val = val;
		this.next = next;
	}
}

迭代法

public class ReverseLinkedList206 {
	public static void main(String[] args){
		ListNode head = initLinkedList(new int[]{1,2,3,4,5});
		printLinkedList(head);
		printLinkedList(reverseList(head));
	}

    //迭代法
	public static ListNode reverseList(ListNode head) {
		return reverse(null,head);
    }
    public static ListNode reverse(ListNode pre, ListNode cur){
    	if (cur == null) {
    		return pre;
    	}
    	ListNode temp = cur.next;
    	cur.next = pre;

    	return reverse(cur,temp);
    }


    public static ListNode initLinkedList(int[] nums){
    	ListNode head = new ListNode(nums[0]);
    	ListNode cur = head,node;
    	for(int i = 1; i < nums.length; i++){
    		node = new ListNode(nums[i]);
    		cur.next = node;
    		cur = node;
    	}
    	return head;
    }
     public static void printLinkedList(ListNode head){
    	ListNode cur = head;
    	while(cur != null){
    		System.out.print(cur.val + "->");
    		cur = cur.next;
    	}
    	System.out.println();
    }
}
class ListNode {
	int val;
	ListNode next;
	public ListNode(){}
	public ListNode(int val){this.val = val;}
	public ListNode(int val, ListNode next){
		this.val = val;
		this.next = next;
	}
}

逆向迭代法

public class ReverseLinkedList206 {
	public static void main(String[] args){
		ListNode head = initLinkedList(new int[]{1,2,3,4,5});
		printLinkedList(head);
		printLinkedList(reverseList(head));
	}

	
    //迭代法（从后向前递归）挺有意思哈
	public static ListNode reverseList(ListNode head) {
		//边界条件判断
		if (head == null) {
			return null;
		}
		if (head.next == null) {
			return head;
		}

		ListNode ret = reverseList(head.next);
		//region 捎带干的事情
		head.next.next = head;
		head.next = null;
		//region 捎带干的事情
		return ret;
    }



    public static ListNode initLinkedList(int[] nums){
    	ListNode head = new ListNode(nums[0]);
    	ListNode cur = head,node;
    	for(int i = 1; i < nums.length; i++){
    		node = new ListNode(nums[i]);
    		cur.next = node;
    		cur = node;
    	}
    	return head;
    }
     public static void printLinkedList(ListNode head){
    	ListNode cur = head;
    	while(cur != null){
    		System.out.print(cur.val + "->");
    		cur = cur.next;
    	}
    	System.out.println();
    }
}
class ListNode {
	int val;
	ListNode next;
	public ListNode(){}
	public ListNode(int val){this.val = val;}
	public ListNode(int val, ListNode next){
		this.val = val;
		this.next = next;
	}
}

这个逆向迭代虽然不好理解。

但是真的很妙。

头插法

//虚拟头节点法（头插法）
    public static ListNode reverseList(ListNode head) {
		ListNode dummyNode = new ListNode(-1,null);
		ListNode cur = head;
		while(cur != null){
			ListNode temp = cur.next;
			//头插法
			cur.next = dummyNode.next;
			dummyNode.next = cur;

			cur = temp;
		}
		return dummyNode.next;
    }

栈法

//栈法
   public static ListNode reverseList(ListNode head) {
	if (head == null || head.next == null) {
		//当只有一个节点或者没有节点的时候直接返回 head 就可以了
		return head;
	}
	ListNode cur = head;
	Stack<ListNode> stack = new Stack<>();

	while (cur != null){
		stack.push(cur);
		cur = cur.next;
	}
	ListNode dummy = new ListNode(-1);
	cur = dummy;
	while(!stack.isEmpty()){
		cur.next = stack.pop();
		cur = cur.next;
	}
	cur.next = null;
	return dummy.next;
   }

体会思想就可以了