反转链表

1、题目

题目要求：
- 反转一个单链表。
示例：
- 输入: 1->2->3->4->5->NULL
- 输出: 5->4->3->2->1->NULL
进阶：你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

2、代码(实现 1)

2.1、思路图解

单链表翻转思路图解：遍历链表，让 nextNode 指向 curNode ，大致流程如下
- 初始状态
- nextNode 指向 curNode ，实现翻转
- curNode、nextNode、nNextNode 指针后移
- 指针后移后 nexNode != null ，继续执行反转
- 翻转完毕，注意，最后需要让 curNode 成为新的首节点，即让 head 指向 curNode
如果数组中只有两个元素时，程序也是可以执行翻转滴

2.2、链表节点的定义

// 节点
class Node{   
    public Integer data;
    public Node next;
    
    public Node(Integer data){
        this.data = data;
    }
    
    public String toString(){
        return data.toString();
    }
}

2.3、翻转链表

// 链表类
class SingleLinkedList{
    
    private Node head = new Node(0);
    
    public void add(Node node){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node preNode = head;
        while(preNode.next != null){            
            preNode = preNode.next;
        }
        preNode.next = node;
    }
    
    public void show(){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node curNode = head.next;
        while(curNode != null){
            System.out.print(curNode.data + "-->");
            curNode = curNode.next;
        }
        System.out.println();
    }
    
    public int length(){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node curNode = head.next;      
        // 链表长度
        int len = 0;
        while(curNode != null){
            len++;
            curNode = curNode.next;
        }
        return len;
    }
    
    public void reverse(){        
        // 链表中没有元素或者只有一个元素
        if (head.next == null || head.next.next == null) {
            return;
        }
        
        // 当前节点
        Node curNode = head.next;        
        // 下个节点
        Node nextNode = curNode.next;    
        // 下下个节点
        Node nNextNode = nextNode.next;
        
        // 首节点翻转后是尾节点
        curNode.next = null;
        
        // 执行翻转
        while(nextNode != null) {
        	// 保存 nNextNode
        	nNextNode = nextNode.next;
        	// nextNode 指向 curNode
        	nextNode.next = curNode;
        	// 指针后移
        	curNode = nextNode;
        	nextNode = nNextNode;
        }
        
        // head 指向新的首节点
        head.next = curNode;
    }
}

2.4、代码测试

代码

public static void main(String[] args) {

    SingleLinkedList singleLinkedList = new SingleLinkedList();

    singleLinkedList.add(new Node(1));
    singleLinkedList.add(new Node(2));
    singleLinkedList.add(new Node(3));
    singleLinkedList.add(new Node(4));
    singleLinkedList.add(new Node(5));

    System.out.println("翻转前~~~");
    singleLinkedList.show();

    System.out.println("翻转后~~~");
    singleLinkedList.reverse();
    singleLinkedList.show();

}

程序运行结果

翻转前~~~
1-->2-->3-->4-->5-->
翻转后~~~
5-->4-->3-->2-->1-->

2.5、全部代码

public class ReverseList {
    public static void main(String[] args) {
        
    	SingleLinkedList singleLinkedList = new SingleLinkedList();
        
    	singleLinkedList.add(new Node(1));
    	singleLinkedList.add(new Node(2));
    	singleLinkedList.add(new Node(3));
    	singleLinkedList.add(new Node(4));	
    	singleLinkedList.add(new Node(5));
    	singleLinkedList.add(new Node(6));
        
        System.out.println("翻转前~~~");
        singleLinkedList.show();
        
        System.out.println("翻转后~~~");
        singleLinkedList.reverse();
        singleLinkedList.show();
        
    }
}

// 链表类
class SingleLinkedList{
    
    private Node head = new Node(0);
    
    public void add(Node node){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node preNode = head;
        while(preNode.next != null){            
            preNode = preNode.next;
        }
        preNode.next = node;
    }
    
    public void show(){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node curNode = head.next;
        while(curNode != null){
            System.out.print(curNode.data + "-->");
            curNode = curNode.next;
        }
        System.out.println();
    }
    
    public int length(){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node curNode = head.next;      
        // 链表长度
        int len = 0;
        while(curNode != null){
            len++;
            curNode = curNode.next;
        }
        return len;
    }
    
    public void reverse(){        
        // 链表中没有元素或者只有一个元素
        if (head.next == null || head.next.next == null) {
            return;
        }
        
        // 当前节点
        Node curNode = head.next;        
        // 下个节点
        Node nextNode = curNode.next;    
        // 下下个节点
        Node nNextNode = nextNode.next;
        
        // 首节点翻转后是尾节点
        curNode.next = null;
        
        // 执行翻转
        while(nextNode != null) {
        	// 保存 nNextNode
        	nNextNode = nextNode.next;
        	// nextNode 指向 curNode
        	nextNode.next = curNode;
        	// 指针后移
        	curNode = nextNode;
        	nextNode = nNextNode;
        }
        
        // head 指向新的首节点
        head.next = curNode;
    }
}

// 节点
class Node{   
    public Integer data;
    public Node next;
    
    public Node(Integer data){
        this.data = data;
    }
    
    public String toString(){
        return data.toString();
    }
}

3、代码(实现 2)

3.1、思路图解

定义一个新的头结点，每次遍历原链表中的节点，取出来作为 reverseHead 的首节点，即每取出一个节点就放在 reverseHead 的后面，这样就实现了链表的反转
- 原链表
- 将 curNode 指向的节点插入在 reverseHead 之后
- curNode、nextNode 指针后移，curNode != null ，可以继续执行翻转操作，将 curNode 指向的节点插入在 reverseHead 之后
- 执行完最后一次翻转后，curNode 指针后移，此时 curNode == null ，翻转结束
- 注意：此时 head 仍然指向之前的首节点，需对其重新赋值：head.next = reverseHead.next;

3.2、链表节点定义

// 节点
class Node{   
    public Integer data;
    public Node next;
    
    public Node(Integer data){
        this.data = data;
    }
    
    public String toString(){
        return data.toString();
    }
}

3.3、翻转链表

// 链表类
class SingleLinkedList{
    
    private Node head = new Node(0);
    
    public void add(Node node){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node preNode = head;
        while(preNode.next != null){            
            preNode = preNode.next;
        }
        preNode.next = node;
    }
    
    public void show(){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node curNode = head.next;
        while(curNode != null){
            System.out.print(curNode.data + "-->");
            curNode = curNode.next;
        }
        System.out.println();
    }
    
    public int length(){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node curNode = head.next;      
        // 链表长度
        int len = 0;
        while(curNode != null){
            len++;
            curNode = curNode.next;
        }
        return len;
    }
    
    public void reverse(){        
        // 链表中没有元素或者只有一个元素
        if (head.next == null || head.next.next == null) {
            return;
        }
        
        // 新的头结点
        Node reverseHead = new Node(0);       
        // 当前待插入的节点
        Node curNode = head.next;     
        // 当前节点的下一个节点
        Node nextNode = curNode.next;
        
        // 执行翻转
        while(curNode != null) {
        	// 保存 curNode 的下一个节点指针
        	nextNode = curNode.next;
        	// 在 preNode 之后插入 curNode
        	curNode.next = reverseHead.next;
        	reverseHead.next = curNode;
        	// 指针后移
        	curNode = nextNode;
        }
        
        head.next = reverseHead.next;
    }
}

3.4、代码测试

代码

public static void main(String[] args) {

    SingleLinkedList singleLinkedList = new SingleLinkedList();

    singleLinkedList.add(new Node(1));
    singleLinkedList.add(new Node(2));
    singleLinkedList.add(new Node(3));
    singleLinkedList.add(new Node(4));	
    singleLinkedList.add(new Node(5));
    singleLinkedList.add(new Node(6));

    System.out.println("翻转前~~~");
    singleLinkedList.show();

    System.out.println("翻转后~~~");
    singleLinkedList.reverse();
    singleLinkedList.show();

}

程序运行结果

翻转前~~~
1-->2-->3-->4-->5-->6-->
翻转后~~~
6-->5-->4-->3-->2-->1-->

3.5、全部代码

public class ReverseList {
    public static void main(String[] args) {
        
    	SingleLinkedList singleLinkedList = new SingleLinkedList();
        
    	singleLinkedList.add(new Node(1));
    	singleLinkedList.add(new Node(2));
    	singleLinkedList.add(new Node(3));
    	singleLinkedList.add(new Node(4));	
    	singleLinkedList.add(new Node(5));
    	singleLinkedList.add(new Node(6));
        
        System.out.println("翻转前~~~");
        singleLinkedList.show();
        
        System.out.println("翻转后~~~");
        singleLinkedList.reverse();
        singleLinkedList.show();
        
    }
}

// 链表类
class SingleLinkedList{
    
    private Node head = new Node(0);
    
    public void add(Node node){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node preNode = head;
        while(preNode.next != null){            
            preNode = preNode.next;
        }
        preNode.next = node;
    }
    
    public void show(){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node curNode = head.next;
        while(curNode != null){
            System.out.print(curNode.data + "-->");
            curNode = curNode.next;
        }
        System.out.println();
    }
    
    public int length(){
        // 首节点指针不能移动哦，需要定义辅助指针
        Node curNode = head.next;      
        // 链表长度
        int len = 0;
        while(curNode != null){
            len++;
            curNode = curNode.next;
        }
        return len;
    }
    
    public void reverse(){        
        // 链表中没有元素或者只有一个元素
        if (head.next == null || head.next.next == null) {
            return;
        }
        
        // 新的头结点
        Node reverseHead = new Node(0);       
        // 当前待插入的节点
        Node curNode = head.next;     
        // 当前节点的下一个节点
        Node nextNode = curNode.next;
        
        // 执行翻转
        while(curNode != null) {
        	// 保存 curNode 的下一个节点指针
        	nextNode = curNode.next;
        	// 在 preNode 之后插入 curNode
        	curNode.next = reverseHead.next;
        	reverseHead.next = curNode;
        	// 指针后移
        	curNode = nextNode;
        }
        
        head.next = reverseHead.next;
    }
}

// 节点
class Node{   
    public Integer data;
    public Node next;
    
    public Node(Integer data){
        this.data = data;
    }
    
    public String toString(){
        return data.toString();
    }
}

4、代码(实现 3)

4.1、思路图解

因为翻转后，原链表的首节点变为新链表的尾节点，所以初始化 preNode = null ，

首先，递归至最深层，curNode == null ，preNode 为原链表的尾节点，此时将原链表的尾节点变为新链表的首节点

回溯至上一步，执行翻转

回溯至最后一步，链表翻转完毕

4.2、链表节点定义

//节点
class Node {
	public Integer data;
	public Node next;

	public Node(Integer data) {
		this.data = data;
	}

	public String toString() {
		return data.toString();
	}
}

4.3、翻转链表

//链表类
class SingleLinkedList {

	private Node head = new Node(0);

	public void add(Node node) {
		// 首节点指针不能移动哦，需要定义辅助指针
		Node preNode = head;
		while (preNode.next != null) {
			preNode = preNode.next;
		}
		preNode.next = node;
	}

	public void show() {
		// 首节点指针不能移动哦，需要定义辅助指针
		Node curNode = head.next;
		while (curNode != null) {
			System.out.print(curNode.data + "-->");
			curNode = curNode.next;
		}
		System.out.println();
	}

	public int length() {
		// 首节点指针不能移动哦，需要定义辅助指针
		Node curNode = head.next;
		// 链表长度
		int len = 0;
		while (curNode != null) {
			len++;
			curNode = curNode.next;
		}
		return len;
	}

	public void reverse() {
		// 翻转后，首节点变成尾节点，所以其 preNode 为 null
		reverse(null, head.next);
	}

	public void reverse(Node preNode, Node curNode) {
		// 首先需要递归至原链表的尾节点
		if (curNode != null) {
			reverse(curNode, curNode.next);
		} else {
			// 递归至最后一个节点，将 head 指向最后一个节点
			head.next = preNode;
			return;
		}
		// 原链表下一个节点直向前一个节点，实现翻转
		curNode.next = preNode;
	}
}

4.4、代码测试

代码

public static void main(String[] args) {

    SingleLinkedList singleLinkedList = new SingleLinkedList();

    singleLinkedList.add(new Node(1));
    singleLinkedList.add(new Node(2));
    singleLinkedList.add(new Node(3));
    singleLinkedList.add(new Node(4));
    singleLinkedList.add(new Node(5));
    singleLinkedList.add(new Node(6));

    System.out.println("翻转前~~~");
    singleLinkedList.show();

    System.out.println("翻转后~~~");
    singleLinkedList.reverse();
    singleLinkedList.show();

}

程序运行结果

翻转前~~~
1-->2-->3-->4-->5-->6-->
翻转后~~~
6-->5-->4-->3-->2-->1-->

4.5、全部代码

public class RecursionReverse {

	public static void main(String[] args) {

		SingleLinkedList singleLinkedList = new SingleLinkedList();

		singleLinkedList.add(new Node(1));
		singleLinkedList.add(new Node(2));
		singleLinkedList.add(new Node(3));
		singleLinkedList.add(new Node(4));
		singleLinkedList.add(new Node(5));
		singleLinkedList.add(new Node(6));

		System.out.println("翻转前~~~");
		singleLinkedList.show();

		System.out.println("翻转后~~~");
		singleLinkedList.reverse();
		singleLinkedList.show();

	}

}

//链表类
class SingleLinkedList {

	private Node head = new Node(0);

	public void add(Node node) {
		// 首节点指针不能移动哦，需要定义辅助指针
		Node preNode = head;
		while (preNode.next != null) {
			preNode = preNode.next;
		}
		preNode.next = node;
	}

	public void show() {
		// 首节点指针不能移动哦，需要定义辅助指针
		Node curNode = head.next;
		while (curNode != null) {
			System.out.print(curNode.data + "-->");
			curNode = curNode.next;
		}
		System.out.println();
	}

	public int length() {
		// 首节点指针不能移动哦，需要定义辅助指针
		Node curNode = head.next;
		// 链表长度
		int len = 0;
		while (curNode != null) {
			len++;
			curNode = curNode.next;
		}
		return len;
	}

	public void reverse() {
		// 翻转后，首节点变成尾节点，所以其 preNode 为 null
		reverse(null, head.next);
	}

	public void reverse(Node preNode, Node curNode) {
		// 首先需要递归至原链表的尾节点
		if (curNode != null) {
			reverse(curNode, curNode.next);
		} else {
			// 递归至最后一个节点，将 head 指向最后一个节点
			head.next = preNode;
			return;
		}
		// 原链表下一个节点直向前一个节点，实现翻转
		curNode.next = preNode;
	}
}

//节点
class Node {
	public Integer data;
	public Node next;

	public Node(Integer data) {
		this.data = data;
	}

	public String toString() {
		return data.toString();
	}
}

原文链接：https://blog.csdn.net/oneby1314/article/details/107577923