元素交换

¶数组

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
并保证奇数和奇数，偶数和偶数之间的相对位置不变。

表面上这是一个很简单的任务,实际上应该夜不难…

但是有意义的事,如何仅在原有的数组之上来进行操作,而不是另外再开放一个空间.

举一个例子.

假设该数组为1,4,5,2,4,5,2

该如何进行操作呢?

我们概念中的交换数组元素的过程应该是这样的.

从第二个元素开始直到最后一个元素为止,如果这个元素为奇数,而前面的数为偶数,那么将这个数和前面的数交换.

这样的过程会将原来的那个数组依次变为

• 1,5,4,2,4,5,2
• 1,5,4,2,5,4,2

目前为止,显然没有完全完成任务.

但如果不断这样做,显然是可以成功的,但时间复杂度未免有点高了.

实际上,不难想到,如果放开相邻元素之间的交换,而改为直接插入会更好…

但是这样做又相当于改变了数组的数据结构.

暂时不大理解…

¶链表元素交换

举个例子说,我要反转一个链表,并且返回反转后的链表的头结点.

a->b->c->d->e

如何反转呢.

首先我们要明白一个事实,就是子节点不知道父节点是谁,所以一定有个变量保存着父节点的引用.

比如要将d->e反转为d<-e,只需让e指向d即可.

然而关键是d又怎么指向c呢?

看起来是个很难理解的问题…那就抽象吧…

我们假设上面的链表为L,有个过程X可以将L反转并且得到其头结点.

接下来就是如何拆解X的过程.

我们尝试这样做,将X分为:

• X1: 用X将L的子节点所连接的链表反转,并且得到其头结点.
• X2: 尾节点指向L的头结点.

看起来这是可行的,再自己看看对于基本情况,也就是输入L为0,1个节点的情况.

0的话返回空,1的话返回该节点

上面的想法是错误的,不应该从后往前推,而应该从前往后推

直接参照别人的代码吧.

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        if not pHead or not pHead.next:
            return pHead
        
        last = None
        while pHead:
            tmp = pHead.next
            pHead = last
            last = pHead
            pHead = tmp

        return last

¶指针

上面两个例子,跟指针都有关…

你对指针的了解很浅显…

现在仔细梳理一下.

先以链表为例,代码如下

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date    : 2018-06-12 11:23:21
# @Author  : yudanqu (943775910@qq.com)
# @Link    : https://www.cnblogs.com/yudanqu/
# @Version : $Id$


class Node(object):
    """节点"""

    def __init__(self, elem):
        self.elem = elem
        self.next = None  # 初始设置下一节点为空

'''
上面定义了一个节点的类，当然也可以直接使用python的一些结构。比如通过元组（elem, None）
'''


# 下面创建单链表，并实现其应有的功能


class SingleLinkList(object):
    """单链表"""

    def __init__(self, node=None):  # 使用一个默认参数，在传入头结点时则接收，在没有传入时，就默认头结点为空
        self.__head = node

    def is_empty(self):
        '''链表是否为空'''
        return self.__head == None

    def length(self):
        '''链表长度'''
        # cur游标，用来移动遍历节点
        cur = self.__head
        # count记录数量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        '''遍历整个列表'''
        cur = self.__head
        while cur != None:
            print(cur.elem, end=' ')
            cur = cur.next
        print("\n")

    def add(self, item):
        '''链表头部添加元素'''
        node = Node(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        '''链表尾部添加元素'''
        node = Node(item)
        # 由于特殊情况当链表为空时没有next，所以在前面要做个判断
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        '''指定位置添加元素'''
        if pos <= 0:
                # 如果pos位置在0或者以前，那么都当做头插法来做
            self.add(item)
        elif pos > self.length() - 1:
            # 如果pos位置比原链表长，那么都当做尾插法来做
            self.append(item)
        else:
            per = self.__head
            count = 0
            while count < pos - 1:
                count += 1
                per = per.next
            # 当循环退出后，pre指向pos-1位置
            node = Node(item)
            node.next = per.next
            per.next = node

    def remove(self, item):
        '''删除节点'''
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判断该节点是否是头结点
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        '''查找节点是否存在'''
        cur = self.__head
        while not cur:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False