How to solve the Node problem in pairwise Exchange list in leetcode

Xiaobian to share with you how to solve the problem of nodes in the two-by-two exchange list in leetcode, I hope you have gained something after reading this article, let's discuss it together!

Title Link

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

Title Description

Given a linked list, swap adjacent nodes pairwise and return the swapped linked list.

You can't just change the internal values of nodes, you need to actually switch nodes.

Examples:

Given 1->2->3->4, you should return 2->1->4->3.

Tag: linked list

The recursive and non-recursive solutions to this problem are similar in principle, both updating the linked list form of each two points to complete the adjustment of the entire linked list.

Recursive solution can be explained as a typical recursive solution

Recursive writing is to observe the recursive solution process at this level and form an abstract model, because the essence of recursion is to repeat the same thing over and over again.[1] Instead of thinking about the complete call stack, level by level, there is no way to start. As shown in the figure, we should focus on the case where the first level calls the small unit, that is, a single f(x).

call stack

There are three main things we should be concerned about:

return value

What did the calling unit do?

termination condition

In this case:

Return value: Sub-linked list completed by exchange

Call unit: Let the two points to be exchanged be head and next, head connects the sub-linked list after the exchange, next connects head, completes the exchange

Termination condition: head is a null pointer or next is a null pointer, that is, there is no node or only one node at present, and the exchange cannot be performed.

code

recursive solution

class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null){ return head; } ListNode next = head.next; head.next = swapPairs(next.next); next.next = head; return next; }}

nonrecursive solution

class Solution { public ListNode swapPairs(ListNode head) { ListNode pre = new ListNode(0); pre.next = head; ListNode temp = pre; while(temp.next != null && temp.next.next != null) { ListNode start = temp.next; ListNode end = temp.next.next; temp.next = end; start.next = end.next; end.next = start; temp = start; } return pre.next; {\cHFFFFFF}{\cHFFFF}

After reading this article, I believe you have a certain understanding of "how to solve the node problem in the two-by-two exchange list in leetcode". If you want to know more about it, welcome to pay attention to the industry information channel. Thank you for reading!