数据结构与算法之美 - 05链表（二）

链表操作练习

这篇主要编写几道单向链表操作练习：

• 单链表Node

  class Node {
      public int data;
      public Node next;
  
      public Node(int data) {
          this.data = data;
      }
  
      public Node(int data, Node next) {
          this.data = data;
          this.next = next;
      }
  }
  

1、单向链表反转

思路： 遍历所有结点，将当前结点的next指针指向前一个结点，操作完成后原尾节点作为反转后的头结点即可。

代码实现：

public static Node reverse(Node list) {
    Node tempNode = list;
    Node preNode = null;
    while (tempNode != null) {
        Node next = tempNode.next;
        tempNode.next = preNode;
        preNode = tempNode;
        tempNode = next;
    }
    return preNode;
}

测试：

//测试数据
public Node getNodeList() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = null;
    return node1;
}


//测试代码
Node list = getNodeList();
printAll(list);
Node reverseList = reverse(list);
printAll(reverseList);

输出：

1 2 3 4 5 
5 4 3 2 1 

2、循环链表检测

检查一个链表是否是循环链表

思路： 通过快、慢指针同时遍历链表，快指针步长为2，慢指针步长为1，当快指针追上慢指针就是循环链表，否则快指针遍历到尾节点（next->null）就非循环链表。

代码实现：

public static boolean checkCircle(Node list) {
    if (list == null) return false;
    Node fast = list.next;
    Node slow = list;
    while (fast != null && fast.next != null) {
        if (fast == slow) return true;
        fast = fast.next.next;
        slow = slow.next;
    }
    return false;
}

测试：

//测试数据
public Node getNodeList() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = node1;
    return node1;
}


//测试代码
Node list = getNodeList();
System.out.println("循环链表：" + checkCircle(list));

输出：

循环链表：true

3、两个有序的链表合并

将两个有序链表，合并成一个有序链表

思路：

• 1、比较两者头结点、以最小的作为head头结点
• 2、定义两个指针p,q，分别指向该链表，定义一个临时指针temp指向头结点
• 3、同时开始遍历这两个链表，如果有一个链表到达尾部，则停止循环
• 4、循环中，如果p指针取内容小于q，则temp.next->p，反之temp.next->q
• 5、循环结束，temp拼接剩余未遍历的p或者q（两链表程度可能不等）
• 6、返回第1步时确认的head头结点

代码实现：

public static Node mergeSortedLists(Node list1, Node list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;

    Node p = list1;
    Node q = list2;

    //确认首节点
    Node head;
    if (p.data <= q.data) {
        head = p;
        p = p.next;
    } else {
        head = q;
        q = q.next;
    }

    //开始排序
    Node tempNode = head;
    while (p != null && q != null) {
        if (p.data <= q.data) {
            tempNode.next = p;
            p = p.next;
        } else {
            tempNode.next = q;
            q = q.next;
        }
        tempNode = tempNode.next;
    }

    //确认剩余尾部
    if (p == null) {
        tempNode.next = q;
    } else {
        tempNode.next = p;
    }
    return head;
}

测试：

//测试数据
public Node getNodeList() {
    Node node1 = new Node(1);
    Node node2 = new Node(3);
    Node node3 = new Node(5);
    Node node4 = new Node(7);
    Node node5 = new Node(9);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = null;
    return node1;
}

public Node getNodeList2() {
    Node node1 = new Node(2);
    Node node2 = new Node(4);
    Node node3 = new Node(6);
    Node node4 = new Node(8);
    Node node5 = new Node(10);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = null;
    return node1;
}

//测试代码
Node list1 = getNodeList();
Node list2 = getNodeList2();
Node mergeNode = mergeSortedLists(list1, list2);
printAll(mergeNode);

输出：

1 2 3 4 5 6 7 8 9 10 

4、删除链表倒数第 n 个结点

思路：

• 1、先定义fast指针，指向正数第n个结点；

• 2、再定义慢指针low执行头结点；

• 3、快慢指针以步长1开始遍历，当fast快指针达到尾结点时，low指针正好在倒数第n个结点位置；

• 4、考虑到单链表删除，需要造作前一个结点，所以在第3步遍历前定一个pre结点指向慢指针low的前一结点；

• 5、当遍历完成有两种情况：第一种，pre指向不为null，low就是要删除的结点，pre则为倒数n-1结点，操作pre结点即可删除low结点；第二种，pre为null,要删除的正好是首结点，将第二个结点作为首节点即可。

代码实现：

public static Node deleteLastKth(Node list, int n) {
    if (list == null || n < 1) return list;

    Node fast = list;
    int i = 1;
    while (fast != null && i < n) {
        fast = fast.next;
        i++;
    }
    //不存在倒数第n个结点
    if (fast == null) return list;

    //开始运算，定位倒数n结点
    Node slow = list;
    Node pre = null;
    while (fast.next != null) {
        fast = fast.next;
        pre = slow;
        slow = slow.next;
    }

    if (pre == null) {
        //倒数n结点正好是首节点
        list = list.next;
    } else {
        //循环结束，slow就为倒数第n个结点，操作pre结点删除slow结点
        pre.next = pre.next.next;
    }

    return list;
} 

测试：

//测试数据
public Node getNodeList() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = null;
    return node1;
}

//测试代码
Node list1 = getNodeList();
Node node = deleteLastKth(list1, 2);
printAll(node);

输出：

1 2 3 5 

5、求链表的中间结点

思路：

1、定义快慢指针fast、slow
2、同时开始遍历，fast步长为2，slow步长为1
3、当快指针fast达到尾部，slow正好在中心结点

代码实现：

public static Node findMiddleNode(Node list) {
    if (list == null) return null;
    Node slow = list;
    Node fast = list;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

测试：

//测试数据
public Node getNodeList() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = null;
    return node1;
}

//测试代码
Node list1 = getNodeList()
printAll(list1);
Node middleNode = findMiddleNode(list1);
System.out.println("middleNode：" + middleNode.data);

输出：

1 2 3 4 5 
middleNode：3