Swap Nodes in Pairs (M)
題目
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
題意
按順序將給定的鏈表中的元素兩兩交換，但不能更改結點中的值，只能對結點本身進行操作，
思路
問題中包含鏈表和子結點等概念，且結點需要變動，很容易想到利用遞回來解決，直接上代碼，
或者直接將結點拆下放到新鏈表中更簡單，
代碼實作
Java
class Solution {
public ListNode swapPairs(ListNode head) {
// 遞回邊界，當待交換結點數不足2時直接回傳
if (head == null || head.next == null) {
return head;
}
ListNode first = head;
ListNode second = first.next;
first.next = swapPairs(second.next);
second.next = first;
return second;
}
}
JavaScript
新鏈表
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function (head) {
let dummy = new ListNode()
let cur = dummy
while (head !== null) {
let a = head, b = head.next
if (b !== null) {
head = b.next
b.next = a
a.next = null
cur.next = b
cur = a
} else {
cur.next = a
head = null
}
}
return dummy.next
}
遞回
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function (head) {
if (head === null) {
return null
}
if (head.next !== null) {
let nextHead = swapPairs(head.next.next)
head.next.next = head
head = head.next
head.next.next = nextHead
}
return head
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/41148.html
標籤：其他