目前单向链表 相邻反转位置

位置两两互换 达到以下效果

基本变换过程为两个两个为一个单位，内部调换然后连接
1-2 => 2-1
3-4 => 4-3
5不变
代码实现

//两两位置互换 
func Swap2Node1(header *Node) *Node {
    if header == nil || header.Data == 0{
        return nil
    }
    cur := &Node{}
    if cur.Data == 0{
        cur = header.Next
        header.Next = header.Next.Next
        cur.Next = header
    } else{
        cur.Next = header
    }
    if cur.Next.Next != nil {
        t := Swap2Node1(cur.Next.Next)
        if t == nil || t.Data != 0{
            cur.Next.Next = t
        }
    }
    return cur
}

一般想到的实现方式 变为以下结果

位置两两互换 达到以下效果

代码如下

//两两位置互换
func Swap2Node(parent *Node,header *Node) *Node {
    if header == nil{
        return nil
    }
    //记录当前位置 作为上一个位置
    prev := Node{Data:header.Data}
    if header.Next != nil{
        //由下一个位置 则与当前位置互换
        temp := Node{Data:header.Next.Data,Next:&prev}
        if parent.Data != 0{
            parent.Next = &temp
        } else{
            parent = &temp
        }
        if header.Next.Next != nil{
            next := Swap2Node(parent.Next,header.Next.Next)
            if next == nil{
                parent.Next.Next = next
            }
        }
    } else{
        //如果没有下一个位置，则该位置不变
        parent.Next.Next = &prev
    }
    return parent
}

单向链表反转实现 达到效果

//位置反转
func ReverseNode(header *Node) *Node {
    currentChain := &Node{}
    for h:= header;h!=nil;h=h.Next{
        if currentChain.Data == 0{
            currentChain = &Node{Data:h.Data}
        } else{
            tempNode := currentChain
            currentChain = &Node{Data:h.Data,Next:tempNode}
        }
    }
    return currentChain
}

* golang 指针作为入参也是值传递，golang里面其实都是值传递，只是指针一般比原始参数小很多，copy代价更低，也方便在不同函数间修改同一个变量

完整代码

package test

import (
    "testing"
    "fmt"
)

type Node struct {
    Data int
    Next *Node
}

func TestChain(t *testing.T)  {
    //单向链表 :1:->:2:->:3:->:4:->:5:->:6:
    header := &Node{Data:1}
    header.Next = &Node{Data:2}
    header.Next.Next = &Node{Data:3}
    header.Next.Next.Next = &Node{Data:4}
    header.Next.Next.Next.Next = &Node{Data:5}
    header.Next.Next.Next.Next.Next = &Node{Data:6}
    for h:= header;h!=nil;h=h.Next{
        fmt.Println("header",h.Data)
    }
    newHeader :=&Node{}
    n := Swap2Node(newHeader,header)
    for h:= n;h!=nil;h=h.Next{
        fmt.Println("Swap2Node new header",h.Data)
    }
    n = ReverseNode(header)
    for h:= n;h!=nil;h=h.Next{
        fmt.Println("ReverseNode new header",h.Data)
    }
    n = Swap2Node1(header)
    for h:= n;h!=nil;h=h.Next{
        fmt.Println("Swap2Node1 new header",h.Data)
    }
}

//两两位置互换
func Swap2Node(parent *Node,header *Node) *Node {
    if header == nil{
        return nil
    }
    //记录当前位置 作为上一个位置
    prev := Node{Data:header.Data}
    if header.Next != nil{
        //由下一个位置 则与当前位置互换
        temp := Node{Data:header.Next.Data,Next:&prev}
        if parent.Data != 0{
            parent.Next = &temp
        } else{
            parent = &temp
        }
        if header.Next.Next != nil{
            next := Swap2Node(parent.Next,header.Next.Next)
            if next == nil{
                parent.Next.Next = next
            }
        }
    } else{
        //如果没有下一个位置，则该位置不变
        parent.Next.Next = &prev
    }
    return parent
}

//位置反转
func ReverseNode(header *Node) *Node {
    currentChain := &Node{}
    for h:= header;h!=nil;h=h.Next{
        if currentChain.Data == 0{
            currentChain = &Node{Data:h.Data}
        } else{
            tempNode := currentChain
            currentChain = &Node{Data:h.Data,Next:tempNode}
        }
    }
    return currentChain
}

//两两位置互换 地址不变
func Swap2Node1(header *Node) *Node {
    if header == nil || header.Data == 0{
        return nil
    }
    cur := &Node{}
    if cur.Data == 0{
        cur = header.Next
        header.Next = header.Next.Next
        cur.Next = header
    } else{
        cur.Next = header
    }
    if cur.Next.Next != nil {
        t := Swap2Node1(cur.Next.Next)
        if t == nil || t.Data != 0{
            cur.Next.Next = t
        }
    }
    return cur
}