This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

First of all, I want to clarify that every algorithm problem has multiple solutions, and we’ll just talk about a few excellent solutions in LeetCode ~, hopefully

Can help you, that we first look at the topic description ~

I. Title Description:

Given a linked list, swap adjacent nodes in pairs and return the swapped list. You can’t just change the values inside a node, you need to actually swap nodes.

The sample a

Input: head = [1,2,3,4] output: [2,1,4,3]Copy the code

Example 2:

Input: head = [] Output: []Copy the code

Example 3:

Input: head = [1] Output: [1]Copy the code

Ii. Analysis of Ideas:

Method one: recursion

Ideas and Algorithms

You can swap nodes in a linked list in pairs recursively.

Recursion terminates when there are no nodes in the list, or only one node in the list, at which point swapping cannot be done.

If there are at least two nodes in the list, the head node of the original list becomes the second node of the new list and the second node of the original list becomes the head node of the new list after the nodes in the list are swapped in pairs. Pairwise swapping of the remaining nodes in the linked list can be done recursively. After the other nodes in the linked list are exchanged in pairs recursively, the pointer relation between nodes is updated to complete the pair-swap of the whole linked list.

If head represents the head node of the original list, the second node of the new list, newHead represents the head node of the new list, and the second node of the original list, the head node of the rest of the original list is Newhead.next. Run head.next = swapPairs(newhead.next) to swap other nodes in pairs. The newHead node is the next node of the head. Then make newhead.next = head, which completes the swap of all nodes. Finally, the head node of the new list, newHead, is returned

code
class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = head.next; head.next = swapPairs(newHead.next); newHead.next = head; return newHead; }}Copy the code
Complexity analysis

Time complexity: O(n)O(n), where nn is the number of nodes in the linked list. You need to update Pointers on each node.

Space complexity: O(n)O(n), where nn is the number of nodes in the linked list. The space complexity depends primarily on the stack space for recursive calls

Method two: iteration

Ideas and Algorithms

It is also possible to swap nodes in a linked list in pairs iteratively.

Create dummy node dummyHead and set dummyHead. Next = head. Set temp to represent the current arrived node. Initially, temp = dummyHead. Two nodes after temp need to be swapped at a time.

If temp is followed by no nodes or only one node, there are no more nodes to swap, so the swap ends. Otherwise, node1 and node2 are obtained after Temp, and the two nodes are swapped by updating the pointer relation of the nodes.

For details, the node relationship before the exchange is temp -> node1 -> node2, and the node relationship after the exchange is temp -> node2 -> node1

temp.next = node2
node1.next = node2.next
node2.next = node1
Copy the code

After the above operations are complete, the node relationship becomes temp -> node2 -> node1. Set temp = node1 to swap the remaining nodes in the linked list in pairs until all nodes are swapped in pairs.

class Solution { public ListNode swapPairs(ListNode head) { ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode temp = dummyHead; while (temp.next ! = null && temp.next.next ! = null) { ListNode node1 = temp.next; ListNode node2 = temp.next.next; temp.next = node2; node1.next = node2.next; node2.next = node1; temp = node1; } return dummyHead.next; }}Copy the code
Complexity analysis

Time complexity: O(n)O(n), where nn is the number of nodes in the linked list. You need to update Pointers on each node.

Space complexity: O(1)O(1)

Brush question summary

If you have other ideas to solve the problem, as long as you can achieve the requirements, it is no problem, all roads lead to Rome, not just limited to the solution I said ha ~, excellent ideas and code is more learning significance, let’s work together