【每日算法Day 36】链表基础1

链表的题目每做一遍都有不一样的感受，一些做过的题目的回头看可能写法不优雅效率也不佳。

LeetCode 206. 反转链表🚩 (opens new window)

题目描述

反转一个单链表。你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

示例

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路

迭代写法：可以使用一个栈保存遍历过的节点，再出栈把它们逆序连接（不过这样做效率低）；还可以使用两个指针将每个节点A的下一个节点B的next指向A节点，在迭代中还需要一个引用保存B的下一个节点以便于指针的移动。时间复杂度为O(n)，空间复杂度为O(1)。

public ListNode reverseList(ListNode head) {
    ListNode prev=null,curr=head;
    while (curr != null) {
        ListNode temp=curr.next;
        curr.next=prev;
        prev=curr;
        curr=temp;
    }
    return prev;
}

递归写法：我们知道递归方法返回的是最终的头结点，也就是原来的尾节点（head.next==null）。那么在一个节点A调用递归方法，得到链表以其下一个节点B为开始的部分的翻转链表的头结点newHead 后，需要做处理将该节点A接到新链表的尾部（也就是B.next）并将newHead返回给上一层调用者。注意A保存了B的引用所以A.next.next=A，每次链接到新链表尾部之后需要把尾部节点.next置为null。时间复杂度为O(n)，空间复杂度为O(n)。

public ListNode reverseList(ListNode head) {
    if (head==null||head.next==null) return head;
    ListNode newHead=reverseList(head.next);
    head.next.next=head;
    head.next=null;
    return newHead;
}

LeetCode 24. 两两交换链表中的节点 (opens new window)

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例

输入：1->2->3->4
输出：2->1->4->3.

解题思路

递归思路：假设当前已经完成了一组两两交换，那么对链表后面剩余的部分我们也是执行相同的操作得到后面新的链表头，把当前完成交换后的尾节点.next指向后面的链表头，再返回本次完成的交换后的新链表头。只有在当前节点为空或当前节点没有下一个节点时递归终止。时间复杂度为O(n)，空间复杂度为O(n)。

public ListNode swapPairs(ListNode head) {
    //递归终止条件
    if (head==null||head.next==null) return head;
    ListNode first=head,second=head.next;
    //递归调用得到后面交换完毕的头结点
    ListNode subHead=swapPairs(second.next);
    //完成本次交换
    second.next=first;
    first.next=subHead;
    return second;
}

迭代思路：仍然使用三个指针来实现交换，用prevNode来保存上一轮交换的尾节点，用firstNode和secondNode来引用本次要交换的两个节点。

public ListNode swapPairs2(ListNode head) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode prevNode = dummy;
    while ((head != null) && (head.next != null)) {
        ListNode firstNode = head;
        ListNode secondNode = head.next;

        prevNode.next = secondNode;
        firstNode.next = secondNode.next;
        secondNode.next = firstNode;

        prevNode = firstNode;
        head = firstNode.next;
    }
    return dummy.next;
}

LeetCode 328. 奇偶链表 (opens new window)

题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

解题思路

将奇数节点依次相连（以head为头结点），将偶数节点依次相连（以dummy为头结点），遍历结束时根据pointer1是否为空判断原链表有偶数个节点还是奇数个节点，进一步知道谁是最后一个奇数节点，把偶数节点形成的链表连在该奇数节点后即可。（不过感觉代码写得不够优雅……）

public ListNode oddEvenList(ListNode head) {
    if (head==null||head.next==null) return head;
    ListNode dummy=new ListNode();
    ListNode pointer1=head,pointer2=dummy;

    ListNode odd=new ListNode(),even;
    while (pointer1 != null && pointer1.next != null) {
        odd = pointer1;
        even = pointer1.next;
        odd.next = even.next;
        pointer1 = odd.next;

        pointer2.next = even;
        pointer2 = pointer2.next;
        pointer2.next = null;
    }

    if (pointer1 == null) {//如果有偶数个节点，则odd为最后一个奇数节点
        odd.next = dummy.next;
    } else {//如果有奇数个节点，则pointer1为最后一个奇数节点
        pointer1.next=dummy.next;
    }
    return head;
}