[LintCode] Swap Two Nodes in Linked List

wua_wua2012 发布于2019-08-14 14:41 / 1307人阅读

摘要：建立结点，指向可能要对进行操作。找到值为和的结点设为，的前结点若和其中之一为，则和其中之一也一定为，返回头结点即可。正式建立，，以及对应的结点，，然后先分析和是相邻结点的两种情况是的前结点，或是的前结点再分析非相邻结点的一般情况。

Problem

Given a linked list and two values v1 and v2. Swap the two nodes in the linked list with values v1 and v2. It"s guaranteed there is no duplicate values in the linked list. If v1 or v2 does not exist in the given linked list, do nothing.

Notice

You should swap the two nodes with values v1 and v2. Do not directly swap the values of the two nodes.

Example

Given 1->2->3->4->null and v1 = 2, v2 = 4.

Return 1->4->3->2->null.

Note

建立dummy结点，指向head（可能要对head进行操作）。
找到值为v1和v2的结点（设为n1，n2）的前结点p1, p2；
若p1和p2其中之一为null，则n1和n2其中之一也一定为null，返回头结点即可。
正式建立n1，n2，以及对应的next结点x1，x2，然后：
先分析n1和n2是相邻结点的两种情况：n1是n2的前结点，或n2是n1的前结点；
再分析非相邻结点的一般情况。
返回dummy.next，结束。

Solution

public class Solution {
    public ListNode swapNodes(ListNode head, int v1, int v2) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p1 = null, p2 = null, cur = dummy;
        while (cur.next != null) {
            if (cur.next.val == v1) p1 = cur;
            else if (cur.next.val == v2) p2 = cur;
            cur = cur.next;
        }
        if (p1 == null || p2 == null) return dummy.next;
        ListNode n1 = p1.next, n2 = p2.next, x1 = n1.next, x2 = n2.next;
        if (p1.next == p2) {
            p1.next = n2;
            n2.next = n1;
            n1.next = x2;
        }
        else if (p2.next == p1) {
            p2.next = n1;
            n1.next = n2;
            n2.next = x1;
        }
        else {
            p1.next = n2;
            n2.next = x1;
            p2.next = n1;
            n1.next = x2;
        }
        return dummy.next;
    }
}

海外云主机云服务器 Nodes linked LintCode LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65154.html

[LintCode] Swap Nodes in Pairs

摘要：指针为，我们选择的两个结点是和。要注意循环的边界条件，这两个结点不能为空。主要思路是先用和两个新结点去保存和两个结点。完成交换之后，连接和，并让前进至此时的结点。 Problem Given a linked list, swap every two adjacent nodes and return its head. Example Given 1->2->3->4, you sh...

EscapedDog 2019-08-14 15:11 评论0 收藏0
[LeetCode/LintCode] Odd Even Linked List

Problem Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. Example Example:Given...

awokezhou 2019-08-16 12:44 评论0 收藏0
[Leetcode] Swap Nodes in Pairs Reverse Nodes in k-

摘要：三指针法复杂度时间空间思路基本的操作链表，见注释。注意使用头节点方便操作头节点。翻转后，开头节点就成了最后一个节点。 Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should ...

TZLLOG 2019-08-14 12:45 评论0 收藏0
[LintCode] Reverse Nodes in k-Group

Problem Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as ...

XGBCCC 2019-08-14 15:12 评论0 收藏0
[LintCode/LeetCode] Partition List

摘要：新建两个链表，分别存和的结点。令头结点分别叫作和，对应的指针分别叫作和。然后遍历，当小于的时候放入，否则放入。最后，让较小值链表尾结点指向较大值链表头结点，再让较大值链表尾结点指向。 Problem Given a linked list and a value x, partition it such that all nodes less than x come before no...

崔晓明 2019-08-14 16:26 评论0 收藏0