反转问题

java

字数统计: 1k阅读时长: 4 min

 2018/01/01 

字符串反转

方法一：递归

原地反转字符串是否代表了空间复杂度为常数？
不，原地反转字符串是一种不使用辅助数据结构的算法。

我们使用递归的方法去反转字符串，它是原地反转，但是空间复杂度却不是常数级空间，因为递归过程中使用了堆栈空间。

算法过程

我们实现递归函数 helper，它接受两个参数：left 左指针和 right 右指针。
如果 left>=right，不做任何操作。
否则交换 s[left] 和 s[right] 和调用 helper(left + 1, right - 1)。

首次调用函数我们传递首尾指针反转整个字符串 return helper(0, len(s) - 1)。


public void helper(char[] s, int left, int right) {
  if (left >= right) return;
  char tmp = s[left];
  s[left++] = s[right];
  s[right--] = tmp;
  helper(s, left, right);
}

public void reverseString(char[] s) {
  helper(s, 0, s.length - 1);
}

复杂度分析

时间复杂度：\mathcal{O}(N)O(N)。执行了 N/2N/2 次的交换。

空间复杂度：\mathcal{O}(N)O(N)，递归过程中使用的堆栈空间。

方法二：双指针法

双指针法是使用两个指针，一个左指针 left，右指针 right，开始工作时 left 指向首元素，right 指向尾元素。交换两个指针指向的元素，并向中间移动，直到两个指针相遇。

算法过程

将 left 指向首元素，right 指向尾元素。
当 left<right：
交换 s[left] 和 s[right]。
left++
right++

// 双指针
func reverseStr(_ s: inout [Character]) -> [Character]{
    var left = 0, right = s.count - 1
    while left < right {
        (s[left],s[right]) = (s[right],s[left])
        left += 1
        right -= 1
    }
    return s
}

测试用例

let str = "123456abcdef"
var characters = Array(str)

print(characters)//["1", "2", "3", "4", "5", "6", "a", "b", "c", "d", "e", "f"]

print(reverseStr(&characters))//["f", "e", "d", "c", "b", "a", "6", "5", "4", "3", "2", "1"]

复杂度分析

时间复杂度：\mathcal{O}(N)O(N)。执行了 N/2N/2 次的交换。
空间复杂度：\mathcal{O}(1)O(1)，只使用了常数级空间。

反转链表

双指针法

定义两个指针pre cur : pre在前 cur 在后
如果cur节点不为空，设置pre.next = cur 实现一次翻转
翻转后pre 、cur同步向前一步
当pre为空终止循环

func reverseList(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil { return head }
    var pre = head, cur: ListNode?
    while pre != nil {
        let temp = pre?.next
        pre?.next = cur
        cur = pre!
        pre = temp
    }
    return cur
}

 递归法核心：reversList(head) = reverseList(head.next)
func reverseList2(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil { return nil }
    let newHead = reverseList2(head?.next)
    head?.next?.next = head
    head?.next = nil
    return newHead
}

反转链表 II

题目描述：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度

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

第一步：找到待反转节点的前一个节点。
第二步：反转m到n这部分。
第三步：将反转的起点的next指向反转的后面一部分。
第四步：将第一步找到的节点指向反转以后的头节点。

public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode node = res;
        //找到需要反转的那一段的上一个节点。
        for (int i = 1; i < m; i++) {
            node = node.next;
        }
        //node.next就是需要反转的这段的起点。
        ListNode nextHead = node.next;
        ListNode next = null;
        ListNode pre = null;
        //反转m到n这一段
        for (int i = m; i <= n; i++) {
            next = nextHead.next;
            nextHead.next = pre;
            pre = nextHead;
            nextHead = next;
        }
        //将反转的起点的next指向next。
        node.next.next = next;
        //需要反转的那一段的上一个节点的next节点指向反转后链表的头结点
        node.next = pre;
        return res.next;
    }