lintcode(511)交换链表当中两个节点

xiaoxiao2021-02-28  91

描述:

给你一个链表以及两个权值v1v2,交换链表中权值为v1v2的这两个节点。保证链表中节点权值各不相同,如果没有找到对应节点,那么什么也不用做。

样例:

给出链表 1->2->3->4->null ,以及 v1 = 2 , v2 = 4 返回结果 1->4->3->2->null

思路:

首先查找是否包含两个目标节点,然后进行交换,但是要考虑两个节点相邻的情况,而且要区分两个节点先后的位置关系。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { /** * @param head a ListNode * @oaram v1 an integer * @param v2 an integer * @return a new head of singly-linked list */ public ListNode swapNodes(ListNode head, int v1, int v2) { // Write your code here ListNode res = new ListNode(0); res.next = head; ListNode node1 = search(res , v1); ListNode node2 = search(res , v2); if(node1 == null || node2 == null){ return head; } ListNode temp1 = node1.next; ListNode temp2 = node2.next; ListNode temp = temp2.next; if(temp1.next == temp2){ node1.next = temp2; temp2.next = temp1; temp1.next = temp; }else if(temp2.next == temp1){ node2.next = temp1; temp = temp1.next; temp1.next = temp2; temp2.next = temp; }else{ node1.next = temp2; temp2.next = temp1.next; node2.next = temp1; temp1.next = temp; } return res.next; } public ListNode search(ListNode head , int value){ while(head.next != null){ if(head.next.val == value){ return head; } head = head.next; } return null; } }

转载请注明原文地址: https://www.6miu.com/read-47896.html

最新回复(0)