// 下面时交换两个数的函数
void swap(int *a, int *b) {
	*a = *a ^ *b;
	*b = *a ^ *b;
	*a = *a ^ *b;
}

当传入的a和b的地址不是同一个地址的情况下，函数正常工作
int a = 1;
int b = 2;
swap(&a, &b);
// 得到a=2，b=1

当传入的a和b的地址是同一个地址的情况下，函数不正常工作
int a = 1;
swap(&a, &a);
// 得到a=0

为什么会这样呢？我们来分析一下
// a=b=0xff，0xff->1
void swap(int *a, int *b) {
	// 0xff->0
	*a = *a ^ *b;
	// 0xff->0
	*b = *a ^ *b;
	// 0xff->0
	*a = *a ^ *b;
}

我们来看看其他情况
int a = 1;
int b = 1;
swap(&a, &b);
// 得到a=1，b=1

为什么会这样呢？我们来分析一下
// a=0xff，0xff->1，b=0xfe，0xfe->1
void swap(int *a, int *b) {
	// 0xff->0，0xfe->1
	*a = *a ^ *b;
	// 0xff->0，0xfe->1
	*b = *a ^ *b;
	// 0xff->1, 0xfe->1
	*a = *a ^ *b;
}

什么是双指针(对撞指针、快慢指针)
双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描，从而达到相应的目的。
换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。
在LeetCode题库中，关于双指针的问题还是挺多的。双指针
img
用法
对撞指针
对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。
对撞数组适用于有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用对撞指针解题
伪代码大致如下：
function fn (list) { var left = 0; var right = list.length - 1; //遍历数组 while (left <= right) { left++; // 一些条件判断 和处理 ... ... right--; }}
举个LeetCode上的例子：
以LeetCode 881救生艇问题为例
由于本题只要求计算出最小船数，所以原数组是否被改变，和元素索引位置都不在考虑位置，所以可以先对于给定数组进行排序，再从数组两侧向中间遍历。所以解题思路如下：
对给定数组进行升序排序
初始化左右指针
每次都用一个”最重的“和一个”最轻的“进行配对，如果二人重量小于Limit，则此时的”最轻的“上船，即(left++)。不管”最轻的“是否上船，”最重的“都要上船，即(right--)并且所需船数量加一，即(num++)
代码如下：
var numRescueBoats = function(people, limit) { people.sort((a, b) => (a - b)); var num = 0 let left = 0 let right = people.length - 1 while (left <= right) { if ((people[left] + people[right]) <= limit) { left++ } right-- num++ } return num};
快慢指针
快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针(fast)和慢指针(slow)，两个指针以不同的策略移动，直到两个指针的值相等(或其他特殊条件)为止，如fast每次增长两个，slow每次增长一个。
以LeetCode 141.环形链表为例,，判断给定链表中是否存在环，可以定义快慢两个指针，快指针每次增长一个，而慢指针每次增长两个，最后两个指针指向节点的值相等，则说明有环。就好像一个环形跑道上有一快一慢两个运动员赛跑，如果时间足够长，跑地快的运动员一定会赶上慢的运动员。
解题代码如下：
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @return {boolean} */var hasCycle = function(head) { if (head === null || head.next === null) { return false } let slow = head let fast = head.next while (slow !== fast) { if (fast === null || fast.next === null) { return false } slow = slow.next fast = fast.next.next } return true};
再比如LeetCode 26 删除排序数组中的重复项，这里还是定义快慢两个指针。快指针每次增长一个，慢指针只有当快慢指针上的值不同时，才增长一个(由于是有序数组，快慢指针值不等说明找到了新值)。
真实代码：
var removeDuplicates = function (nums) { if (nums.length === 0) { return 0; } let slow = 0; for (let fast = 0; fast < nums.length; fast++) { if (nums[fast] !== nums[slow]) { slow++; nums[slow] = nums[fast]; } } return slow + 1;};
总结
当遇到有序数组时，应该优先想到双指针来解决问题，因两个指针的同时遍历会减少空间复杂度和时间复杂度。
相关题目
LeetCode.141.环形链表
LeetCode.026.删除数组中重复的项
LeetCode.881.救生艇
参考文献
《LeetBook》双指针
【算法总结--数组相关】双指针法的常见应用。
1.4.2 双指针技巧(二)

在leetcode 中， 快慢指针和双指针的related topics都是two pointers， 其实两种算法的应用场景还是有很大不同， 所以本篇文章单独把快慢指针列出来。
快慢指针方法也被称为 Hare & Tortoise 算法，该算法会使用两个在数组（或序列/链表）中以不同速度移动的指针。该方法在处理循环链表或数组时非常有用。
该算法的应用场景：
处理链表或数组中的循环的问题
找链表中点或需要知道特定元素的位置
何时应该优先选择这种方法，而不是上面提到的二指针方法？
有些情况不适合使用二指针方法，比如在不能反向移动的单链接链表中。使用快速和慢速模式的一个案例是当你想要确定一个链表是否为回文（palindrome）时。
例如：判断一个链表中是否有环， 迭代的方式如图：
fast 指针每次移动两格， slow指针每次移动一格， 如果存在环路， 则fast最终一定会和slow相遇。
下面看几道例题：
一、 判断链表是否有环
leet code 第141题 - 难度 easy
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}
二、返回一个存在环路的链表中环路开始的位置
来源： leet code - 142 题 - 难度 medium
描述： Given a linked list, return the node where the cycle begins. If there is no cycle, return null.   To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
思路：
首先， 用快慢指针我们可以判断出链表中是否有环， 假设在z 点 fast指针和slow 指针相遇。x-y 长度为a， y-z 长度为 b ， z-y 长度为c。
则：slow 指针走了 a+b 的距离。 fast 指针走了 a + n（b + c）+ b 的距离。（可能不仅绕了一圈而是绕环走了n圈）
fast指针的速度是slow 指针速度的2倍。 所以a + b + n（b + c） = 2 （a + b）， 简化得 a+b = n（b + c）。 因为我们想要求 a 的距离，  所以我们移动方程 得到  a = （n-1）b + n c 。 
仔细观察上面的等式。 考虑它的含义， 即c 总比b 多一次， 这就意味着， 我们再放两个指针， first放在x ，second放在z ，这次保持速度一致， first 跑到y ， second 也会跑到y。所以，当它们相遇，就是cycle的起点。
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null ) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        // 找到相遇点z （对应上图）
        while(true) {
            if(fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        // 想到 cycle起点y （对应上图）
        slow = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
        
    }
三、 判断链表是否是回文链表
来源： leet code 第234 题 - 难度 easy 
描述： Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
解题思路：用快慢指针找到链表的中点， 把后半部分链表逆序，再和前半部分链表做比较是否每个元素都相等。
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        // 1. 找到链表中点。 比如length=4，找到的slow指针的index为1，length5，找到的slow指针index为2
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 2。从中点位置后的第一个元素开始反转后面的链表
        slow = slow.next;
        ListNode p = slow;
        ListNode q = p.next;
        while(q!= null) {
            ListNode tmp = q.next;
            q.next = p;
            p = q;
            q= tmp;
        }
        slow.next = null;
       // 3。 只要后面的元素和前半部分都相等， 则链表是回文链表
        while(p!= null){
            if(p.val != head.val) {
                return false;
            }
            p = p.next;
            head = head.next;
        }
        return true;
    }

想了解更多数据结构以及算法题，可以关注微信公众号“数据结构和算法”，每天一题为你精彩解答。
问题描述
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8,
listA = [4,1,8,4,5],
listB = [5,0,1,8,4,5],
skipA = 2, skipB = 3输出：Reference of the node with value = 8输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B
为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2,
listA = [0,9,1,2,4],
listB = [3,2,4],
skipA = 3, skipB = 1输出：Reference of the node with value = 2输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B
为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0,
listA = [2,6,4],
listB = [1,5],
skipA = 3, skipB = 2输出：null输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal
必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
1，通过集合set解决
上面说了一大堆，其实就是判断两个链表是否相交，如果相交就返回他们的相交的交点，如果不相交就返回null。
做这题最容易想到的一种解决方式就是先把第一个链表的节点全部存放到集合set中，然后遍历第二个链表的每一个节点，判断在集合set中是否存在，如果存在就直接返回这个存在的结点。如果遍历完了，在集合set中还没找到，说明他们没有相交，直接返回null即可，原理比较简单，直接看下代码
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //创建集合set
    Set<ListNode> set = new HashSet<>();
    //先把链表A的结点全部存放到集合set中
    while (headA != null) {
        set.add(headA);
        headA = headA.next;
    }

    //然后访问链表B的结点，判断集合中是否包含链表B的结点，如果包含就直接返回
    while (headB != null) {
        if (set.contains(headB))
            return headB;
        headB = headB.next;
    }
    //如果集合set不包含链表B的任何一个结点，说明他们没有交点，直接返回null
    return null;
}
2，先统计两个链表的长度
还可以先统计两个链表的长度，如果两个链表的长度不一样，就让链表长的先走，直到两个链表长度一样，这个时候两个链表再同时每次往后移一步，看节点是否一样，如果有相等的，说明这个相等的节点就是两链表的交点，否则如果走完了还没有找到相等的节点，说明他们没有交点，直接返回null即可，来画个图看一下。
最后再来看下代码
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //统计链表A和链表B的长度
    int lenA = length(headA), lenB = length(headB);

    //如果节点长度不一样，节点多的先走，直到他们的长度一样为止
    while (lenA != lenB) {
        if (lenA > lenB) {
            //如果链表A长，那么链表A先走
            headA = headA.next;
            lenA--;
        } else {
            //如果链表B长，那么链表B先走
            headB = headB.next;
            lenB--;
        }
    }

    //然后开始比较，如果他俩不相等就一直往下走
    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }
    //走到最后，最终会有两种可能，一种是headA为空，
    //也就是说他们俩不相交。还有一种可能就是headA
    //不为空，也就是说headA就是他们的交点
    return headA;
}

//统计链表的长度
private int length(ListNode node) {
    int length = 0;
    while (node != null) {
        node = node.next;
        length++;
    }
    return length;
}
3，双指针解决
我们还可以使用两个指针，最开始的时候一个指向链表A，一个指向链表B，然后他们每次都要往后移动一位，顺便查看节点是否相等。如果链表A和链表B不相交，基本上没啥可说的，我们这里假设链表A和链表B相交。那么就会有两种情况，
一种是链表A的长度和链表B的长度相等，他们每次都走一步，最终在相交点肯定会相遇。
一种是链表A的长度和链表B的长度不相等，如下图所示
虽然他们有交点，但他们的长度不一样，所以他们完美的错开了，即使把链表都走完了也找不到相交点。
我们仔细看下上面的图，如果A指针把链表A走完了，然后再从链表B开始走到相遇点就相当于把这两个链表的所有节点都走了一遍，同理如果B指针把链表B走完了，然后再从链表A开始一直走到相遇点也相当于把这两个链表的所有节点都走完了
所以如果A指针走到链表末尾，下一步就让他从链表B开始。同理如果B指针走到链表末尾，下一步就让他从链表A开始。只要这两个链表相交最终肯定会在相交点相遇，如果不相交，最终他们都会同时走到两个链表的末尾，我们来画个图看一下
如上图所示，A指针和B指针如果一直走下去，那么他们最终会在相交点相遇，最后再来看下代码
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //tempA和tempB我们可以认为是A,B两个指针
    ListNode tempA = headA;
    ListNode tempB = headB;
    while (tempA != tempB) {
        //如果指针tempA不为空，tempA就往后移一步。
        //如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB）
        tempA = tempA == null ? headB : tempA.next;
        //指针tempB同上
        tempB = tempB == null ? headA : tempB.next;
    }
    //tempA要么是空，要么是两链表的交点
    return tempA;
}
注意：这里所说的指针并不是C语言中的指针，在这里其实他就是一个变量，千万不要搞混了。
问题分析
第一种解法应该是都容易想到的，但效率不高，一个个存储，然后再拿另一个链表的节点一个个判断。最后一种解法没有统计链表的长度，而是当一个链表访问完如果没有找到相交点，就从下一个链表继续访问，一般不太容易想到，也算是比较经典的。