leetcode - 链表两两元素交换 + 判断链表有无环

链表两两元素交换

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

/**
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 * <b>你不能只是单纯的改变节点内部的值</b>，而是需要实际的进行节点交换。
 * 解题除了使用递归, 另一种思路就是保证在替换的过程中, 节点不会丢失
 * @param head
 * @return
 */
public static ListNode swapPairs(ListNode head) {
    if(head == null) {
        return null;
    }
    ListNode result = new ListNode(0);
    result.next = head;
    ListNode cur = result;
    while(cur.next != null && cur.next.next != null) {
        // 第一个节点
        ListNode temp = cur.next;
        // 第二个节点
        ListNode pre  = temp.next;
        // 当前节点的下个节点是第二个节点
        cur.next = pre;
        // 第一个节点的下个节点是第三个节点
        temp.next = pre.next;
        // 第二个节点的下个节点是第一个节点
        pre.next = temp;
        // 当前节点等于第一个节点
        cur = temp;
    }
    return result.next;
}

环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

 ```
 /**
  * 给定一个链表，判断链表中是否有环。
  * 1. 龟兔赛跑的方式, 一个一次走两步, 一个一次走一步, 如果相遇说明有环, 否则直到null说明无环
  * 2. 使用set存储数据, 之后遍历, 查找有无相同的节点
  * 两种方案的时间复杂度都是O(n), 空间复杂度第一种会好点
  *
  * 执行用时 :1 ms, 在所有 java 提交中击败了78.04%的用户
  * 内存消耗 :37 MB, 在所有 java 提交中击败了97.08%的用户
  * @param head
  * @return
  */
 public static boolean hasCycle(ListNode head) {
     if(head == null) {
         return false;
     }
     ListNode fast = head;
     ListNode low = head;
     while(fast != null && low != null && fast.next != null) {
         fast = fast.next.next;
         low = low.next;
         if(fast != null && fast.equals(low)) {
             return true;
         }
     }
     return false;
 }

 /**
  * 执行用时 :6 ms, 在所有 java 提交中击败了25.71%的用户
  * 内存消耗 :38 MB, 在所有 java 提交中击败了94.68%的用户
  * @param head
  * @return
  */
 public static boolean hasCycle1(ListNode head) {
     if(head == null) {
         return false;
     }
     Set set = new HashSet<ListNode>();
     while(head.next != null) {
         set.add(head);
         head = head.next;
         if(set.contains(head)) {
             return true;
         }
     }
     return false;
 }

```