【链表】打卡2：如何优雅着反转单链表

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢

【题目描述】

反转单链表。例如链表为：

1->2->3->4

反转后为

4->3->2->1

【要求】

如果链表的长度为 N, 时间复杂度达到 O(n), 额外空间复杂度达到 O(1)

【难度】

士：★☆☆☆

解答

方法1

这道题还是挺简单的，当我们在反转一个结点的时候，把一个结点的后继改为指向它前驱就可以了。这里需要注意的点就是，当你把当前结点的后继指向前驱的时候，这个时候链表会被截断，也就是说后面的结点和当前结点分开了，所以我们需要一个变量来保存当前结点的后继，以防丢失。

具体代码如下：

代码如下

class Node{
	public int value;
	public Node next;
	public Node(int data){
		this.value = data;
	}
}

主要代码

//反转单链表
public static Node reverseList(Node head){
    Node next = null;//指向当前结点的后继
    Node pre = null;//指向当前结点的前驱
    while(head!=null){
        next = head.next;
        //当前结点的后继指向前驱
        head.next = pre;

        pre = head;
        //处理下一个结点
        head = next;
    }
    return pre;
}

运行过程

方法二

这道题也可以用递归来做，假设 方法 reverse() 的功能是将单链表进行逆转。采用递归的方法时，我们可以不断着对子链表进行递归。例如对于如下的链表：

我们对子链表 2->3->4 进行递归，即
Node newList = reverse(head.next)。递归之后的结果如下：

逆转之后子链表 2->3->变为了 4->3->2。
注意，我刚才假设 reverse() 的功能就是对链表进行逆转。不过此时结点 1 仍然是指向结点 2 的。这个时候，我们再把结点1 和 2逆转一下，然后 1 的下一个结点指向 null 就可以了。如图：

递归的结束条件就是：当子链表只有一个结点，或者为 null 时，递归结束。代码如下：

//用递归的方法反转链表
public static Node reverseList2(Node head){
    if(head == null || head.next == null){
        return head;
    }
    //递归反转子链表
    //第四次递归返回结果为    1 -> 2 -> 3 <- 4  
    //head:3,next=nodeList,nodeList:4 null
    //第三次递归返回结果为    1 -> 2 <- 3 <- 4  
    //...
    Node nodeList = reverseList2(head.next);

    head.next.next = head;	//head:3 nodeList,nodeList:4 head,
    head.next = null; 		//head:3 null,    nodeList:4 head,head:3 null
    return nodeList;
}

测试代码

public static void main(String[] args) {
    int i = 1;
    Node head = new Node(i);		
    Node node = head;
    while(++i<5){
        node.next = new Node(i);
        node = node.next;
    }
    node = reverseList2(head);
    while(node!=null){
        System.out.println(node.value);
        node = node.next;
    }
}

运行截图

第四次递归返回：

第四次递归处理返回：

第三次递归返回：

问题拓展

题目：反转部分链表结点

【题目描述】

题目：给定一个单向链表的头结点head,以及两个整数from和to ,在单项链表上把第from个结点和第to个结点这一部分进行反转

例如：
1->2->3->4->5->null,from=2,to=4

结果：1->4->3->2->5->null

例如：

1->2->3->null from=1,to=3

结果为3->2->1->null

【要求】

1、如果链表长度为N，时间复杂度要求为O（N),额外空间复杂度要求为O（1）

2、如果不满足1<=from<=to<=N,则不调整

【难度】

士：★☆☆☆

【解答】

//反转部分链表结点
public static Node reversePartList(Node head,int from,int to){
    if(head == null){
        return head;
    }
    int length = 0;//记录链表的长度
    Node node = head;
    Node pre = null;//记录from前一个结点
    Node aft = null;//记录to后一个结点
    while(node != null){
        length++;
        if(length == from-1){
            pre = node;
        }
        if(length == to+1){
            aft = node;
        }
        node = node.next;
    }
    //判断给定的值是否合理
    if(from < 1 || from >= to ||  to > length){
        return head;
    }
    //把from到to这部分链表进行反转
    node = pre == null ? head : pre.next;//node指向部分链表的第一个结点
    Node cur = node.next;//cur指向当前要处理的结点
    node.next = aft;//先处理第一个结点
    Node next = null;
    while(cur != aft){
        next = cur.next;//保存当前结点的下一个结点
        cur.next = node;
        node = cur;
        cur = next;
    }
    if(pre != null){//说明反转的中间
        pre.next = node;
        return head;
    }
    return node;
}

【运行图片】

来源：苦逼的码农（ID:di201805）

（完）