反转链表-四种方法

反转链表

链接

题目：描述

给定一个单链表的头结点head，长度为n，反转该链表后，返回新链表的表头。

以上转换过程如下图所示：

示例1

输入：

{1,2,3}
1

返回值：

{3,2,1}
1

示例2

输入：

{}
1

返回值：

{}
1

复制

说明：

空链表则输出空       
1

1.迭代法

因为单链表只能由当前节点查找到后一个节点，因此使用迭代法时，需要保存当前节点的后一个节点。

1. curr 指向链表的当前节点，next 保存curr节点的下一个节点（因为是单链表，不保存的话，改变方向之后就找不到旧节点的下个节点了），prev刚开始值为空，保存当前节点的前一个节点。

2. 假如单链表为[1,2,3,4,5],curr指向第一个节点1，核心代码如下：

	next = curr.next //先保存next节点，防止节点断后，找不到下一个节点
	curr.next = prev
    prev = curr, curr = next
1
2
3

Java代码实现：

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
//      如何调整链表指针，达到链表反转的目的。
        ListNode prev = null; // prev : 指向反转好节点的最后一个节点
        ListNode curr = head;    //指向反转链表的第一个节点
        while(curr != null){
            ListNode next = curr.next; 
            curr.next = prev;
            
            prev = curr;
            curr = next;
        }
        return prev;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Python代码如下：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr is not None:
            next = curr.next
            curr.next = prev

            prev, curr = curr, next
        return prev     # 注意：此时prev节点指向最后一个节点
1
2
3
4
5
6
7
8
9
10

2.使用“栈”

由于栈的特点：先入后出，假如要反转的链表为[1, 2, 3, 4, 5]，我们把每个节点压入到栈中，然后再取出就可以得到反转后的节点[5, 4, 3, 2, 1]。具体步骤如下：

1. 遍历链表，把每个节点依次压入栈中。
2. 再遍历取出，就实现了链表的反转

代码如下：
java实现：

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.Stack;
public class Solution {
    public ListNode ReverseList(ListNode head) {
    Stack<ListNode> stack = new Stack<>();    // 栈
//     1.把链表中的节点入栈
    while(head != null){
        stack.push(head);
        head = head.next;
    }
//     2.判断栈为空，则返回null
    if(stack.isEmpty())
        return null;
//     3.从栈中取出元素，然后组成链表，则为反转后的链表
    ListNode dummy = stack.pop();
    ListNode temp = dummy;
    while(!stack.isEmpty()){
        temp.next = stack.pop();
        temp = temp.next;
    }
//  4.最后一个节点的next要置为空，否则会构成环
    temp.next = null;
    return dummy;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Python代码：

    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        stack = []  #使用列表即可实现栈
        while head is not None:
            stack.append(head)
            head = head.next
        if len(stack) == 0:
            return None
        dummy = stack.pop()  # 哑结点
        temp = dummy
        while len(stack) != 0:
            temp.next = stack.pop()
            temp = temp.next
#       最后一个节点是反转前的头结点，一定要让他的next等于空，否则会构成环
        temp.next = None
        return dummy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.新建链表法

如图所示：遍历单链表中的每一个节点，一个一个进行链接，如下图所示：

Python代码如下：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 双链表法：
        dummy = None            # 定义空节点
        while head is not None:
            next = head.next    # 因为是单链表，先保存下一个节点
            head.next = dummy   # 第一个节点连接到 dummy

            dummy, head = head, next    # dummy 指向最新的节点，head指向下一个节点，进行遍历
        return dummy    # 结束后 dummy 将指向新节点的头结点
1
2
3
4
5
6
7
8
9
10

java代码：

class Solution {
    public ListNode reverseList(ListNode head) {
        // 1.定义哑结点 dummy
        ListNode dummy = null;
        while(head != null){
            // 2.先保存下一个节点
            ListNode next = head.next;
            // 3.原链表中的第一个节点指向dummy
            head.next = dummy;
            // 4.dummy 指向 head，head指向下一个节点
            dummy = head;
            head = next;
        }
        return dummy;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4.递归法

如图所示
思路：

• 开始head指向第一个节点
• 递归到倒数第二个节点
• 然后改变节点的方向
• 找到递归的出口，反方向回来

def reverse_list(self, head):  
  
    if head is None or head.next is None:    # 递归结束条件  
 return head  
    else:  
        ans = self.reverse_list(head.next)   # 递归下一个结点 到 倒数第二个结点  
  
 head.next.next = head                # 最后一个结点指向倒数第二个结点  
 head.next = None # 最后一结点的指针域赋值为空  
 return ans
1
2
3
4
5
6
7
8
9
10

结果如下：

码字不易，感觉不错可以加个关注哈！