剑指offer—反转链表 解答

剑指offer—反转链表

反转链表一

题目描述

输入一个链表,反转链表后,输出新链表的表头。

思路

  • 方法一:使用辅助空间遍历链表并保存,再次循环翻转插入链表

时间复杂度和空间复杂度都较大,不推荐使用

  • 方法二:迭代一次链表,用指针保存前一个和后一个的引用,然后通过迭代反转链表指向

时间复杂度O(N),空间复杂度O(1),我们就使用该方法

执行翻转一个节点的关键代码

在看具体算法之前,有必要先弄清楚链接反转的原理以及需要哪些指针。举例而言,有一个三个不同结点组成的链表 A → B → C,需要反转结点中的链接成为 A ← B ← C

假设我们有两个指针,一个指向结点A,一个指向结点B。 分别记为 prehead。则可以用这两个指针简单地实现 A 和 B 之间的链接反转:

ListNode node = head.next;//保存下一个节点的引用(用于把head往后移动)
head.next = pre;//把head next节点指向前驱节点
pre = head;//把pre移动到head节点上
head = node;//把head节点移动到下一个节点上

只需要迭代执行该过程,整个链表就被翻转了

代码

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        while(head!=null){
            ListNode node = head.next;
            head.next = pre;
            pre = head;
            head = node;
        }
        return pre;
    }
}

反转链表二

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路

根据要求只循环一次,那就只能使用第一题的思想,当然可以使用O(1)的辅助空间

  • 反转节点还是使用上面的思想,只是我们需要在反转节点结束后把m前面和n后面的节点调整到正确的位置

  • 注意我们要引入两个额外指针,分别称为 startPrestartNextstartNext 指针指向从链表头起的第m个结点,此结点是反转后链表的尾部。startPre 指针指向第 m 个结点的前一个结点,此结点是新链表的头部。

  • 两个指针都已经到达最终位置。我们完成了子链表的反转工作。然而,还有一些链接需要调整。下图展示了利用 startPrestartNext 指针完成链接调整的过程。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null){
            return null;
        }
        ListNode h,pre,startPre,startNext;
        h = startNext = head; pre = null; startPre = new ListNode(0);//startPre初始化,为空的话无法调整位置
        int i = 1;
        while(i<=n+1){//前n次翻转,第n+1次调整m、n外面的节点位置
            if(i<=m){
                pre = head;
                head = head.next;
                if(i<m){
                    startPre = pre;//保存startPre位置
                    startNext = startNext.next;//保存startNext位置
                }
            }else if(i<=n){//开始翻转
                ListNode node = head.next;
                head.next = pre;
                pre = head;
                head = node;
            }else{//调整位置
                startPre.next = pre;//指向开始反转的前一个节点,这个节点就是新的反转链表的前面一个节点
                startNext.next = head;//指向开始反转的第一个节点,反转结束需要与链表末尾连接
            }
            i++;
        }
        return m==1?pre:h;//当m==1时,第一个节点就被反转,pre节点就是反转链表的头结点,否则h保存的head节点就是头结点
        // if(head==null){
        //     return null;
        // }
        // final ListNode h = head;
        // ListNode pre = null;
        // ListNode startPre = new ListNode(0);
        // ListNode startNext = head;
        // int i = 1;
        // while(head!=null){
        //     if(i<m){
        //         pre = head;
        //         head = head.next;
        //         if(i<m){
        //             // startPre = pre;
        //             startNext = startNext.next;
        //         }else if(i==m){
        //             startPre = pre;
        //         }
        //     }else if(i<=n){
        //         final ListNode node = head.next;
        //         head.next = pre;
        //         startPre.next = head;
        //         pre = head;
        //         head = node;
        //     }else{
        //         startNext.next = head;
        //         head = head.next;
        //     }
        //     i++;
        // }
        // return h;
    }
}